<!DOCTYPE html>
<html lang="zh-cn"><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="referrer" content="never">
    <meta name="description" content="在程序员这一职业中，集合是我们使用频率相当高的一个工具，而其中的HashMap，则更是我们用以处理业务逻辑的好帮手，同时HashMap的底层实现和原理，也成了面试题中的常客。

还在担心面试中被问">
    <meta property="og:description" content="在程序员这一职业中，集合是我们使用频率相当高的一个工具，而其中的HashMap，则更是我们用以处理业务逻辑的好帮手，同时HashMap的底层实现和原理，也成了面试题中的常客。

还在担心面试中被问">
    <meta http-equiv="Cache-Control" content="no-transform">
    <meta http-equiv="Cache-Control" content="no-siteapp">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <title>HashMap面试题，看这一篇就够了！ - 天之痕苏的小院子 - 博客园</title>
    <link id="favicon" rel="shortcut icon" href="https://common.cnblogs.com/favicon.svg" type="image/svg+xml">
    
    <link rel="stylesheet" href="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/blog-common.css">
    <link id="MainCss" rel="stylesheet" href="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/bundle-codinglife.css">
    
    <link id="mobile-style" media="only screen and (max-width: 767px)" type="text/css" rel="stylesheet" href="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/bundle-codinglife-mobile.css">
    
    <link type="application/rss+xml" rel="alternate" href="https://www.cnblogs.com/tianzhihensu/rss">
    <link type="application/rsd+xml" rel="EditURI" href="https://www.cnblogs.com/tianzhihensu/rsd.xml">
    <link type="application/wlwmanifest+xml" rel="wlwmanifest" href="https://www.cnblogs.com/tianzhihensu/wlwmanifest.xml">
    <script src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/osd.js"></script><script async="" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/analytics.js"></script><script>
        var currentBlogId = 218355;
        var currentBlogApp = 'tianzhihensu';
        var cb_enable_mathjax = false;
        var isLogined = false;
        var isBlogOwner = false;
        var skinName = 'CodingLife';
        var visitorUserId = '';
    </script>
        <script>
            var currentPostDateAdded = '2019-12-02 07:26';
        </script>
    <script src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/jquery-2.js"></script>
    <script src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/blog-common.js"></script><style type="text/css">.medium-zoom-overlay{position:fixed;top:0;right:0;bottom:0;left:0;opacity:0;transition:opacity .3s;will-change:opacity}.medium-zoom--opened .medium-zoom-overlay{cursor:pointer;cursor:zoom-out;opacity:1}.medium-zoom-image{cursor:pointer;cursor:zoom-in;transition:transform .3s cubic-bezier(.2,0,.2,1)!important}.medium-zoom-image--hidden{visibility:hidden}.medium-zoom-image--opened{position:relative;cursor:pointer;cursor:zoom-out;will-change:transform}</style>
    
    
    
<meta http-equiv="origin-trial" content="A+b/H0b8RPXNaJgaNFpO0YOFuGK6myDQXlwnJB3SwzvNMfcndat4DZYMrP4ClJIzYWo3/yP2S+8FTZ/lpqbPAAEAAABueyJvcmlnaW4iOiJodHRwczovL2ltYXNkay5nb29nbGVhcGlzLmNvbTo0NDMiLCJmZWF0dXJlIjoiVHJ1c3RUb2tlbnMiLCJleHBpcnkiOjE2MjYyMjA3OTksImlzVGhpcmRQYXJ0eSI6dHJ1ZX0="><meta http-equiv="origin-trial" content="A9ZgbRtm4pU3oZiuNzOsKcC8ppFSZdcjP2qYcdQrFKVzkmiWH1kdYY1Mi9x7G8+PS8HV9Ha9Cz0gaMdKsiVZIgMAAAB7eyJvcmlnaW4iOiJodHRwczovL2RvdWJsZWNsaWNrLm5ldDo0NDMiLCJmZWF0dXJlIjoiVHJ1c3RUb2tlbnMiLCJleHBpcnkiOjE2MjYyMjA3OTksImlzU3ViZG9tYWluIjp0cnVlLCJpc1RoaXJkUGFydHkiOnRydWV9"><meta http-equiv="origin-trial" content="AxL6oBxcpn5rQDPKSAs+d0oxNyJYq2/4esBUh3Yx5z8QfcLu+AU8iFCXYRcr/CEEfDnkxxLTsvXPJFQBxHfvkgMAAACBeyJvcmlnaW4iOiJodHRwczovL2dvb2dsZXRhZ3NlcnZpY2VzLmNvbTo0NDMiLCJmZWF0dXJlIjoiVHJ1c3RUb2tlbnMiLCJleHBpcnkiOjE2MjYyMjA3OTksImlzU3ViZG9tYWluIjp0cnVlLCJpc1RoaXJkUGFydHkiOnRydWV9"><meta http-equiv="origin-trial" content="A9KPtG5kl3oLTk21xqynDPGQ5t18bSOpwt0w6kGa6dEWbuwjpffmdUpR3W+faZDubGT+KIk2do0BX2ca16x8qAcAAACBeyJvcmlnaW4iOiJodHRwczovL2dvb2dsZXN5bmRpY2F0aW9uLmNvbTo0NDMiLCJmZWF0dXJlIjoiVHJ1c3RUb2tlbnMiLCJleHBpcnkiOjE2MjYyMjA3OTksImlzU3ViZG9tYWluIjp0cnVlLCJpc1RoaXJkUGFydHkiOnRydWV9"><meta http-equiv="origin-trial" content="A3HucHUo1oW9s+9kIKz8mLkbcmdaj5lxt3eiIMp1Nh49dkkBlg1Fhg4Fd/r0vL69mRRA36YutI9P/lJUfL8csQoAAACFeyJvcmlnaW4iOiJodHRwczovL2RvdWJsZWNsaWNrLm5ldDo0NDMiLCJmZWF0dXJlIjoiQ29udmVyc2lvbk1lYXN1cmVtZW50IiwiZXhwaXJ5IjoxNjI2MjIwNzk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><script src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/pubads_impl_2021030201.js" async=""></script><link rel="preload" href="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/integrator.js" as="script"><script type="text/javascript" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/integrator.js"></script></head>
<body class="has-navbar">
    <a name="top"></a>
        <div id="bannerbar" class="bannerbar-mobile formobile">
            <a href="https://www.cnblogs.com/cmt/p/14408628.html" target="_blank" onclick="ga('send', 'event', 'Link', 'click', 'aws-blog-mobile-banner')">
                <img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/35695-20210101110709031-1748833382.jpg" alt="">
            </a>
        </div>
    <div id="top_nav" class="navbar forpc">
        <nav id="nav_main" class="navbar-main">
            <ul id="nav_left" class="navbar-list navbar-left">
                <li class="navbar-branding"><a href="https://www.cnblogs.com/" title="开发者的网上家园"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/logo.svg" alt="博客园Logo"></a></li>
                <li><a href="https://www.cnblogs.com/" onclick="ga('send', 'event', 'Link', 'click', 'skin-navbar-sitehome')">首页</a></li>
                <li><a href="https://news.cnblogs.com/" onclick="ga('send', 'event', 'Link', 'click', 'skin-navbar-news')">新闻</a></li>
                <li><a href="https://q.cnblogs.com/" onclick="ga('send', 'event', 'Link', 'click', 'skin-navbar-q')">博问</a></li>
                <li><a id="nav_brandzone" href="https://brands.cnblogs.com/" onclick="ga('send', 'event', 'Link', 'click', 'skin-navbar-brands')">专区</a></li>
                <li><a href="https://ing.cnblogs.com/" onclick="ga('send', 'event', 'Link', 'click', 'skin-navbar-ing')">闪存</a></li>
                <li><a href="https://edu.cnblogs.com/" onclick="ga('send', 'event', 'Link', 'click', 'skin-navbar-edu')">班级</a></li>
            </ul>
            <ul id="nav_right" class="navbar-list navbar-right">
                <li>
                    <form id="zzk_search" class="navbar-search" action="https://zzk.cnblogs.com/s" method="get">
                        <input name="w" id="zzk_search_input" placeholder="代码改变世界" type="text" tabindex="3">
                        <button type="submit" id="zzk_search_button">
                            <img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/search.svg" alt="搜索">
                        </button>
                    </form>
                </li>
                <li id="navbar_login_status" class="navbar-list">
                    <a id="navblog-myblog-icon" class="navbar-user-info navbar-blog" href="https://passport.cnblogs.com/GetBlogApplyStatus.aspx" alt="我的博客" title="我的博客" style="display: none;">
                        <img id="myblog_icon" class="navbar-icon" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/myblog.svg" alt="我的博客">
                    </a>
                    <a class="navbar-user-info navbar-blog" href="https://i.cnblogs.com/EditPosts.aspx?opt=1" alt="写随笔" title="写随笔" style="display: none;">
                        <img id="new_post_icon" class="navbar-icon" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/newpost.svg" alt="写随笔">
                    </a>
                    <a class="navbar-user-info navbar-message navbar-icon-wrapper" href="https://msg.cnblogs.com/" alt="短消息" title="短消息" style="display: none;">
                        <img id="msg_icon" class="navbar-icon" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/message.svg" alt="短消息">
                        <span id="msg_count" style="display: none"></span>
                    </a>
                    <div id="user_info" class="navbar-user-info dropdown" style="display: none;">
                        <a class="dropdown-button" href="https://home.cnblogs.com/">
                            <img id="user_icon" class="navbar-avatar" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/avatar-default.svg" alt="用户头像">
                        </a>
                        <div class="dropdown-menu">
                            <a id="navblog-myblog-text" href="https://passport.cnblogs.com/GetBlogApplyStatus.aspx">我的博客</a>
                            <a href="https://home.cnblogs.com/">我的园子</a>
                            <a href="https://account.cnblogs.com/settings/account">账号设置</a>
                            <a href="javascript:void(0)" onclick="logout();">退出登录</a>
                        </div>
                    </div>
                    <a class="navbar-anonymous" href="https://account.cnblogs.com/signup/" style="display: inline;">注册</a>
                    <a class="navbar-anonymous" href="javascript:void(0);" onclick="login()" style="display: inline;">登录</a>
                </li>
            </ul>
        </nav>
    </div>

    
    <!--done-->
<div id="home">
<div id="header">
	<div id="blogTitle">
        <a id="lnkBlogLogo" href="https://www.cnblogs.com/tianzhihensu/"><img id="blogLogo" src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/logo.gif" alt="返回主页"></a>		
		
<!--done-->
<h1><a id="Header1_HeaderTitle" class="headermaintitle HeaderMainTitle" href="https://www.cnblogs.com/tianzhihensu/">天之痕苏</a>
</h1>
<h2>来自某BAT互联网大厂的一枚程序员，注重总结、分享和自我成长，长期不间断的投资自己，未来可期。</h2>




		
	</div><!--end: blogTitle 博客的标题和副标题 -->
	<div id="navigator">
		
<ul id="navList">
<li><a id="blog_nav_sitehome" class="menu" href="https://www.cnblogs.com/">
博客园</a>
</li>
<li>
<a id="blog_nav_myhome" class="menu" href="https://www.cnblogs.com/tianzhihensu/">
首页</a>
</li>
<li>

<a id="blog_nav_newpost" class="menu" href="https://i.cnblogs.com/EditPosts.aspx?opt=1">
新随笔</a>
</li>
<li>
<a id="blog_nav_contact" class="menu" href="https://msg.cnblogs.com/send/%E5%A4%A9%E4%B9%8B%E7%97%95%E8%8B%8F%E7%9A%84%E5%B0%8F%E9%99%A2%E5%AD%90">
联系</a></li>
<li>
<a id="blog_nav_rss" class="menu" href="javascript:void(0)" data-rss="https://www.cnblogs.com/tianzhihensu/rss/">
订阅</a>
<!--<partial name="./Shared/_XmlLink.cshtml" model="Model" /></li>--></li>
<li>
<a id="blog_nav_admin" class="menu" href="https://i.cnblogs.com/">
管理</a>
</li>
</ul>


		<div class="blogStats">
			<div id="blog_stats_place_holder"><script>loadBlogStats();</script></div>
		</div><!--end: blogStats -->
	</div><!--end: navigator 博客导航栏 -->
</div><!--end: header 头部 -->
<div id="main">
	<div id="mainContent">
	<div class="forFlow">
		<div id="post_detail">
    <!--done-->
    <div id="topics">
        <div class="post">
            <h1 class="postTitle">
                
<a id="cb_post_title_url" class="postTitle2 vertical-middle" href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">
    <span>HashMap面试题，看这一篇就够了！</span>
    


</a>

            </h1>
            <div class="clear"></div>
            <div class="postBody">
                    <div id="cnblogs_post_description" style="display: none">
        在程序员这一职业中，集合是我们使用频率相当高的一个工具，而其中的HashMap，则更是我们用以处理业务逻辑的好帮手，同时HashMap的底层实现和原理，也成了面试题中的常客。

还在担心面试中被问到HashMap、HashTable等知识点吗？还在为不知道HashMap的底层实现原理而不自信吗？相信你看完这篇文章，一定会对HashMap有更深刻的认识。

本场Chat中，主要介绍HashMap的如下内容：
- JDK7、JDK8中HashMap的底层实现原理、扩容机制以及异同点；
- HashMap、HashTable是什么关系？
- HashMap的线程不安全以及潜在的风险；
- 如何规避HashMap的线程不安全？

适合人群：准备Java面试者、初中级Java开发者
    </div>
<div id="cnblogs_post_body" class="blogpost-body cnblogs-markdown">
<blockquote>
<p>更多2019年的技术文章，欢迎关注我的微信公众号：码不停蹄的小鼠松（微信号：busy_squirrel），也可扫下方二维码关注获取最新文章哦~</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191006125707747.png" width="20%"></p>
</blockquote>
<p>文章目录：<br>
@</p><div class="toc"><div class="toc-container-header">目录</div><ul><li><a href="#序言">序言</a></li><li><a href="#一、jdk7中的hashmap底层实现">一、JDK7中的HashMap底层实现</a><ul><li><a href="#11-基础知识">1.1 基础知识</a></li><li><a href="#12-put方法">1.2 put()方法</a><ul><li><a href="#121-特殊key值处理">1.2.1 特殊key值处理</a></li><li><a href="#122-扩容">1.2.2 扩容</a></li><li><a href="#123-如何计算bucket下标？">1.2.3 如何计算bucket下标？</a><ul><li><a href="#①-hash值的计算">① hash值的计算</a></li><li><a href="#②-取模的逻辑">② 取模的逻辑</a></li><li><a href="#③-拓展">③ 拓展</a></li></ul></li><li><a href="#124-在目标bucket中遍历entry结点">1.2.4 在目标bucket中遍历Entry结点</a></li></ul></li><li><a href="#13-get方法">1.3 get()方法</a></li><li><a href="#14-map中的迭代器iterator">1.4 Map中的迭代器Iterator</a><ul><li><a href="#141-map遍历的几种方式">1.4.1 Map遍历的几种方式</a><ul><li><a href="#方式1：iterator迭代器">方式1：Iterator迭代器</a></li><li><a href="#方式2：最常见的使用方式，可同时得到key、value值">方式2：最常见的使用方式，可同时得到key、value值</a></li><li><a href="#方式3：使用foreach方式（jdk18才有）">方式3：使用foreach方式（JDK1.8才有）</a></li><li><a href="#方式4：通过key的set集合遍历">方式4：通过key的set集合遍历</a></li></ul></li><li><a href="#142-iterator的实现原理">1.4.2 Iterator的实现原理</a></li></ul></li><li><a href="#15-fail-fast策略">1.5 fail-fast策略</a></li></ul></li><li><a href="#二、jdk8中的hashmap底层实现">二、JDK8中的HashMap底层实现</a><ul><li><a href="#21-put操作">2.1 put()操作</a></li><li><a href="#22-扩容操作">2.2 扩容操作</a></li><li><a href="#23-get操作">2.3 get()操作</a></li></ul></li><li><a href="#三、hashmap、hashtable是什么关系？">三、HashMap、HashTable是什么关系？</a><ul><li><a href="#31-共同点与异同点">3.1 共同点与异同点</a></li><li><a href="#32-hashmap的线程安全">3.2 HashMap的线程安全</a></li></ul></li><li><a href="#四、hashmap线程不安全在哪？">四、HashMap线程不安全在哪？</a><ul><li><a href="#41-数据覆盖问题">4.1 数据覆盖问题</a></li><li><a href="#42-扩容时导致死循环">4.2 扩容时导致死循环</a></li><li><a href="#43-小结">4.3 小结</a></li></ul></li><li><a href="#五、如何规避hashmap的线程不安全？">五、如何规避HashMap的线程不安全？</a><ul><li><a href="#51-将map转为包装类">5.1 将Map转为包装类</a></li><li><a href="#52-使用concurrenthashmap">5.2 使用ConcurrentHashMap</a></li></ul></li><li><a href="#reference">Reference</a></li></ul></div><p></p>
<h1 id="序言">序言</h1>
<p>在后端的日常开发工作中，<strong>集合</strong>是使用频率相当高的一个工具，而其中的<strong>HashMap</strong>，则更是我们用以处理业务逻辑的好帮手，同时<strong>HashMap</strong>的底层实现和原理，也成了面试题中的常客。</p>
<p>以前曾有详细了解过<strong>HashMap</strong>的实现原理，看过源码（JDK7版本）。但随着jdk版本的飞速迭代（现在都到JDK13了，但新特性还从没用过。。），主流的jdk使用版本也终于从JDK7挪到了JDK8。</p>
<p>由于JDK的向前兼容，在JDK8的使用过程中也没发现<strong>HashMap</strong>有什么特别之处，特性并无变化（依然线程不安全）。但最近的一次好奇心驱使，从IDE中点进去看了下<strong>HashMap</strong>的<strong><code>put()</code></strong>方法，有点儿懵逼，怎么跟我记忆中的不太一样？从JDK7到JDK8，<strong>HashMap</strong>也做了升级么？升级了什么哪些内容？</p>
<p>借着这股好奇心，把JDK7和JDK8的源码都翻了翻，对两者的实现原理做一下对比，JDK版本都在半年左右一次的速度推陈出新，我们的认知当然也要跟上，不断学习，站在浪潮之巅，不然就要被这滚滚的信息泥石流给裹挟淹没了。</p>
<p>先展示下Map家族的关系层级，有助于我们更好的理解后面的内容。</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094229472.png" class="medium-zoom-image" width="60%"></p>
<p><strong>HashMap</strong>的基本知识点介绍就不多啰嗦了，直奔主题，看JDK7和JDK8的功能实现吧。</p>
<h1 id="一、jdk7中的hashmap底层实现">一、JDK7中的HashMap底层实现</h1>
<h2 id="11-基础知识">1.1 基础知识</h2>
<p>不管是1.7，还是1.8，HashMap的实现框架都是<strong>哈希表 + 链表</strong>的组合方式。结构图如下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094309793.png" class="medium-zoom-image" width="70%"></p>
<p>平常使用最多的就是<strong><code>put()</code></strong>、<strong><code>get()</code></strong>操作，想要了解底层实现，最直接的就是从<strong><code>put()/get()</code></strong>方法看起。不过在具体看源码前，我们先关注几个域变量，打打基础，如下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094335204.png" class="medium-zoom-image" width="60%"></p>
<p>上图中，已对各个变量做了简单的解释。<br>
再多说一下，最后一个变量<strong><code>modCount</code></strong>，记录了map新增/删除k-v对，或者内部结构做了调整的次数，其主要作用，是对Map的<strong><code>iterator()</code></strong>操作做一致性校验，如果在iterator操作的过程中，map的数值有修改，直接抛出<strong><code>ConcurrentModificationException</code></strong>异常。</p>
<p>还需要说明的是，上面的域变量中存在一个等式：</p>
<pre><code class="language-java hljs">threshold = table.length * loadFactor;
</code></pre>
<p>当执行<strong><code>put()</code></strong>操作放入一个新的值时，如果map中已经存在对应的key，则作替换即可，若不存在，则会首先判断<strong><code>size&gt;=threshold</code></strong>是否成立，这是决定哈希table是否扩容的重要因素。</p>
<p>就使用层面来说，用的最多的莫过于<strong><code>put()</code></strong>方法、<strong><code>get()</code></strong>方法。想要详细了解运作原理，那就先从这两个方法看起吧，这两个方法弄明白了，也就基本能理清HashMap的实现原理了。</p>
<h2 id="12-put方法">1.2 put()方法</h2>
<p>当了解了以上的变量和用途后，接下来看下<strong><code>put()</code></strong>方法的具体实现：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094430765.png" class="medium-zoom-image" width="60%"></p>
<p>如上面的截图代码所示，整个put方法的处理过程，可拆分为四部分：</p>
<ul>
<li><strong>part1：特殊key值处理，key为null；</strong></li>
<li><strong>part2：计算table中目标bucket的下标；</strong></li>
<li><strong>part3：指定目标bucket，遍历Entry结点链表，若找到key相同的Entry结点，则做替换；</strong></li>
<li><strong>part4：若未找到目标Entry结点，则新增一个Entry结点。</strong></li>
</ul>
<p>不知大家有没有发现，上面截图中的<strong><code>put()</code></strong>方法是有返回值的，场景区分如下：</p>
<ul>
<li>场景1：若执行put操作前，key已经存在，那么在执行put操作时，会使用本次的新value值来覆盖前一次的旧value值，返回的就是旧value值；</li>
<li>场景2：若key不存在，则返回null值。</li>
</ul>
<p>下面对put方法的各部分做详细的拆解分析。</p>
<h3 id="121-特殊key值处理">1.2.1 特殊key值处理</h3>
<p>特殊key值，指的就是key为null。<br>
先说结论：<br><br>
<strong>a)</strong> HashMap中，是允许key、value都为null的，且key为null只存一份，多次存储会将旧value值覆盖；<br><br>
<strong>b)</strong> key为null的存储位置，都统一放在下标为<strong>0</strong>的bucket，即：table[0]位置的链表；<br><br>
<strong>c)</strong> 如果是第一次对key=null做put操作，将会在table[0]的位置新增一个Entry结点，使用头插法做链表插入。</p>
<p>上代码：</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">private</span> V <span class="hljs-title">putForNullKey</span><span class="hljs-params">(V value)</span> </span>{
    <span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e = table[<span class="hljs-number">0</span>]; e != <span class="hljs-keyword">null</span>; e = e.next) {
        <span class="hljs-keyword">if</span> (e.key == <span class="hljs-keyword">null</span>) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(<span class="hljs-keyword">this</span>);
            <span class="hljs-keyword">return</span> oldValue;
        }
    }
    modCount++;
    addEntry(<span class="hljs-number">0</span>, <span class="hljs-keyword">null</span>, value, <span class="hljs-number">0</span>);
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
}


<span class="hljs-comment">/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">addEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>{
    <span class="hljs-keyword">if</span> ((size &gt;= threshold) &amp;&amp; (<span class="hljs-keyword">null</span> != table[bucketIndex])) {
        resize(<span class="hljs-number">2</span> * table.length);
        hash = (<span class="hljs-keyword">null</span> != key) ? hash(key) : <span class="hljs-number">0</span>;
        bucketIndex = indexFor(hash, table.length);
    }


    createEntry(hash, key, value, bucketIndex);
}


<span class="hljs-comment">/**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization).  This version needn't worry about resizing the table.
 *
 * Subclass overrides this to alter the behavior of HashMap(Map),
 * clone, and readObject.
 */</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">createEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>{
    Entry&lt;K,V&gt; e = table[bucketIndex];
    table[bucketIndex] = <span class="hljs-keyword">new</span> Entry&lt;&gt;(hash, key, value, e);
    size++;
}
</code></pre>
<p><strong><code>putForNullKey()</code></strong>方法中的代码较为简单：首先选择<strong>table[0]</strong>位置的链表，然后对链表做遍历操作，如果有结点的key为null，则将新value值替换掉旧value值，返回旧value值，如果未找到，则新增一个key为null的Entry结点。</p>
<p>重点我们看下第二个方法<strong><code>addEntry()</code></strong>。<br>
这是一个通用方法：</p>
<blockquote>
<p>给定hash、key、value、bucket下​标，新增一个Entry结点，另外还担负了扩容职责。如果哈希表中存放的k-v对数量超过了当前阈值(<strong>threshold = table.length * loadFactor</strong>)，且当前的bucket下标有链表存在，那么就做扩容处理（resize）。扩容后，重新计算hash，最终得到新的bucket下标，然后使用头插法新增结点。</p>
</blockquote>
<h3 id="122-扩容">1.2.2 扩容</h3>
<p>上一节有提及，当k-v对的容量超出一定限度后，需要对哈希table做扩容操作。那么问题来了，怎么扩容的？<br>
下面看下源代码：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/2019120209451255.png" class="medium-zoom-image" width="60%"></p>
<p>有两个核心点：<br>
<strong><font color="red">a)</font></strong> 扩容后大小是扩容前的2倍；</p>
<pre><code class="language-java hljs">oldCapacity=table.length;
newCapacity = <span class="hljs-number">2</span> * oldCapacity;
</code></pre>
<p><strong><font color="red">b)</font></strong> 数据搬迁，从旧table迁到扩容后的新table。<br>
为避免碰撞过多，先决策是否需要对每个Entry链表结点重新hash，然后根据hash值计算得到bucket下标，然后使用头插法做结点迁移。</p>
<h3 id="123-如何计算bucket下标？">1.2.3 如何计算bucket下标？</h3>
<h4 id="①-hash值的计算">① hash值的计算</h4>
<p>首先得有key的hash值，就是一个整数，int类型，其计算方式使用了一种可尽量减少碰撞的算式（高位运算），具体原理不再展开，只要知道一点就行：使用key的hashCode作为算式的输入，得到了hash值。</p>
<p>从以上知识点，我们可以得到一个<strong><font color="green">推论</font></strong>：<br><br>
<strong><font color="red">对于两个对象，若其hashCode相同，那么两个对象的hash值就一定相同。</font></strong></p>
<p>这里还牵涉到另外一个知识点。对于HashMap中key的类型，必须满足以下的条件：<br><br>
<strong><font color="red">若两个对象逻辑相等，那么他们的hashCode一定相等，反之却不一定成立。</font></strong></p>
<p>逻辑相等的含义就比较宽泛了，我们可以将逻辑的相等定义为两个对象的内存地址相同，也可以定义为对象的某个域值相等，自定义两个对象的逻辑相等，可通过重写<strong><code>Object</code></strong>类的<strong><code>equals()</code></strong>方法来实现。<br>
比如<strong><code>String</code></strong>类，请看以下代码：</p>
<pre><code class="language-java hljs">String str1 = <span class="hljs-string">"abc"</span>;
String str2 = <span class="hljs-keyword">new</span> String(<span class="hljs-string">"abc"</span>);
System.out.println(str1 == str2);  <span class="hljs-comment">// false，两个对象的内存地址并不同</span>
System.out.println(str1.equals(str2)); <span class="hljs-comment">// true 两个对象的域值相同，都存储了 abc 这三个字符</span>
</code></pre>
<p>对于上面代码中的<strong><code>str1</code></strong>、<strong><code>str2</code></strong>两个对象，虽然它们的内存地址不同，但根据<strong><code>String</code></strong>类中对<strong><code>Object</code></strong>类的<strong><code>equals()</code></strong>方法的重写(<strong>@override</strong>)，两个对象的域变量（即char数组）都存储了'a'、'b'、'c'三个字符，因此逻辑上是相等的。既然<strong><code>str1</code></strong>、<strong><code>str2</code></strong>两个对象逻辑上相等，那么一定有如下结果：</p>
<pre><code class="language-java hljs">System.out.println(str1.hashCode() == str2.hashCode());


---输出---
<span class="hljs-keyword">true</span>
</code></pre>
<p>从而我们就可以知道，在同一个HashMap对象中，会有如下结果：</p>
<pre><code class="language-java hljs">String str1 = <span class="hljs-string">"abc"</span>;
String str2 = <span class="hljs-keyword">new</span> String(<span class="hljs-string">"abc"</span>);
Map&lt;String, Integer&gt; testMap = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();
testMap.put(str1, <span class="hljs-number">12</span>);
testMap.put(str2, <span class="hljs-number">13</span>);


String str3 = <span class="hljs-keyword">new</span> StringBuilder(<span class="hljs-string">"ab"</span>).append(<span class="hljs-string">"c"</span>).toString();
System.out.println(testMap.get(str3));


---输出---
<span class="hljs-number">13</span>
</code></pre>
<p>另外，我们也可以反过来想一下。</p>
<p>假设HashMap的key不满足上面提到的条件，即：两个对象相等的情况下，他们的hashCode可能不一致。那么，这会带来什么后果呢？以上面示例代码中的<strong><code>str1</code></strong>、<strong><code>str2</code></strong>为例，若它们的hashCode不相等，那么对应的hash也就可能不相等（<strong>注意</strong>：这里是<strong>可能不相等</strong>，也有可能相等），testMap做put操作时，<strong><code>str1</code></strong>、<strong><code>str2</code></strong>为就会被分配到不同的bucket上，导致的最直接后果就是会存储两份。间接的后果那就更多了，比如：使用<strong><code>str3</code></strong>对象执行<strong><code>testMap.get(str3)</code></strong>操作时，可能获取不到值，更进一步的后果就是这部分无法触达的对象无法回收，导致<strong>内存泄漏</strong>。</p>
<p>因此，<strong><font color="red">再重新一遍</font></strong>，HashMap的key所对应的类型，一定要满足如下条件：<br><br>
<strong><font color="red">若两个对象逻辑相等，那么他们的hashCode一定相等，反之却不一定成立。</font></strong></p>
<h4 id="②-取模的逻辑">② 取模的逻辑</h4>
<p>前面我们分析了hash值的计算，接下来就可以引出bucket下标的计算：</p>
<pre><code class="language-java hljs"><span class="hljs-comment">/**
 * Returns index for hash code h.
 */</span>
<span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">indexFor</span><span class="hljs-params">(<span class="hljs-keyword">int</span> h, <span class="hljs-keyword">int</span> length)</span> </span>{
    <span class="hljs-keyword">return</span> h &amp; (length-<span class="hljs-number">1</span>);
}
</code></pre>
<p>计算相当简洁：将table的容量与hash值做“<strong>与</strong>”运算，得到哈希table的bucket下标。</p>
<h4 id="③-拓展">③ 拓展</h4>
<p>这种通俗的不能再通俗的计算大家都能看懂，但为何要这样做呢？背后的思考是什么？在看到下面的解释前，大家可以先思考下~</p>
<p>在文档开头，给出了HashMap类中的各个域变量。其中，哈希table的初始大小默认设置为16，为2的次幂数。后面在扩容时，都是以2的倍数来扩容。为什么非要将哈希table的大小控制为2的次幂数？</p>
<p><strong><font color="green">原因1</font></strong>：降低发生碰撞的概率，使散列更均匀。根据key的hash值计算bucket的下标位置时，使用“与”运算公式：h &amp; (length-1)，当哈希表长度为2的次幂时，等同于使用表长度对hash值取模（不信大家可以自己演算一下），散列更均匀；<br><br>
<strong><font color="green">原因2</font></strong>：表的长度为2的次幂，那么(length-1)的二
进制最后一位一定是1，在对hash值做“与”运算时，最后一位就可能为1，也可能为0，换句话说，取模的结果既有偶数，又有奇数。设想若
(length-1)为偶数，那么“与”运算后的值只能是0，奇数下标的bucket就永远散列不到，会浪费一半的空间。</p>
<h3 id="124-在目标bucket中遍历entry结点">1.2.4 在目标bucket中遍历Entry结点</h3>
<p>先把这部分代码拎出来：</p>
<pre><code class="language-java hljs">...
<span class="hljs-keyword">int</span> i = indexFor(hash, table.length);
<span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e = table[i]; e != <span class="hljs-keyword">null</span>; e = e.next) {
    Object k;
    <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(<span class="hljs-keyword">this</span>);
        <span class="hljs-keyword">return</span> oldValue;
    }
}
...
</code></pre>
<p>通过hash值计算出下标，找到对应的目标bucket，然后对链表做遍历操作，逐个比较，如下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094602498.png" class="medium-zoom-image" width="70%"></p>
<p>注意这里的查找条件：<strong><font color="red"><code>e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))</code></font></strong><br>
结点的key与目标key的相等，要么内存地址相等，要么逻辑上相等，两者有一个满足即可。</p>
<h2 id="13-get方法">1.3 get()方法</h2>
<p>相比于<strong><code>put()</code></strong>方法，<strong><code>get()</code></strong>方法的实现就相对简单多了。主要分为两步，先是通过key的hash值计算目标bucket的下标，然后遍历对应bucket上的链表，逐个对比，得到结果。</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">get</span><span class="hljs-params">(Object key)</span> </span>{
    <span class="hljs-keyword">if</span> (key == <span class="hljs-keyword">null</span>)
        <span class="hljs-keyword">return</span> getForNullKey();
    Entry&lt;K,V&gt; entry = getEntry(key);


    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span> == entry ? <span class="hljs-keyword">null</span> : entry.getValue();
}


<span class="hljs-comment">/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */</span>
<span class="hljs-function"><span class="hljs-keyword">final</span> Entry&lt;K,V&gt; <span class="hljs-title">getEntry</span><span class="hljs-params">(Object key)</span> </span>{
    <span class="hljs-keyword">int</span> hash = (key == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : hash(key);
    <span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)];
         e != <span class="hljs-keyword">null</span>;
         e = e.next) {
        Object k;
        <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;
            ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
            <span class="hljs-keyword">return</span> e;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
}
</code></pre>
<h2 id="14-map中的迭代器iterator">1.4 Map中的迭代器Iterator</h2>
<h3 id="141-map遍历的几种方式">1.4.1 Map遍历的几种方式</h3>
<p>先问个问题，你能想到几种遍历Map的方式？</p>
<h4 id="方式1：iterator迭代器">方式1：Iterator迭代器</h4>
<pre><code class="language-java hljs">Iterator&lt;Entry&lt;String, Integer&gt;&gt; iterator = testMap.entrySet().iterator();
<span class="hljs-keyword">while</span> (iterator.hasNext()) {
    Entry&lt;String, Integer&gt; next = iterator.next();
    System.out.println(next.getKey() + <span class="hljs-string">":"</span> + next.getValue());
}
</code></pre>
<p>逐个获取哈希table中的每个bucket中的每个Entry结点，后面会详细介绍。</p>
<h4 id="方式2：最常见的使用方式，可同时得到key、value值">方式2：最常见的使用方式，可同时得到key、value值</h4>
<pre><code class="language-java hljs"><span class="hljs-comment">// 方式一</span>
<span class="hljs-keyword">for</span> (Map.Entry&lt;String, Integer&gt; entry : testMap.entrySet()) {
    System.out.println(entry.getKey() + <span class="hljs-string">":"</span> + entry.getValue());
}
</code></pre>
<p>这种方式是一个语法糖，我们可通过反编译命令javap，或通过IDE来查下编译之后的语句：</p>
<pre><code class="language-java hljs">Iterator var2 = testMap.entrySet().iterator();
<span class="hljs-keyword">while</span>(var2.hasNext()) {
    Entry&lt;String, Integer&gt; entry = (Entry)var2.next();
    System.out.println((String)entry.getKey() + <span class="hljs-string">":"</span> + entry.getValue());
}
</code></pre>
<p>其底层还是使用的是Iterator功能。</p>
<h4 id="方式3：使用foreach方式（jdk18才有）">方式3：使用foreach方式（JDK1.8才有）</h4>
<pre><code class="language-java hljs">testMap.forEach((key, value) -&gt; {
    System.out.println(key + <span class="hljs-string">":"</span> + value);
});
</code></pre>
<p>这是一种Lambda表达式。foreach也是一个语法糖，其内部是使用了<strong>方式二</strong>的处理方式，Map的foreach方法实现如下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094643507.png" class="medium-zoom-image" width="65%"></p>
<h4 id="方式4：通过key的set集合遍历">方式4：通过key的set集合遍历</h4>
<pre><code class="language-java hljs">Iterator&lt;String&gt; keyIterator = testMap.keySet().iterator();
<span class="hljs-keyword">while</span> (keyIterator.hasNext()) {
    String key = keyIterator.next();
    System.out.println(key + <span class="hljs-string">":"</span> + testMap.get(key));
}
</code></pre>
<p>这种也是Iterator的方式，不过是通过Set类的iterator方式。</p>
<p>相比<strong>方式1</strong>，这种方式在获取<code>value</code>时，还需要再次通过<strong><code>testMap.get()</code></strong>的方式，性能相比<strong>方式1</strong>要降低很多。但两者有各自的使用场景，若在Map的遍历中仅使用<code>key</code>，则<strong>方式4</strong>较为适合，若需用到<code>value</code>，推荐使用<strong>方式1</strong>。</p>
<p>从前面的<strong>方式1</strong>和<strong>方式2</strong>可知，方式4还有如下的变体（语法糖的方式）：</p>
<pre><code class="language-java hljs"><span class="hljs-keyword">for</span> (String key : testMap.keySet()) {
    System.out.println(key + <span class="hljs-string">":"</span> + testMap.get(key));
}
</code></pre>
<p>综合以上，在遍历Map时，从性能方面考虑，若需同时使用key和value，推荐使用<strong>方式1</strong>或<strong>方式2</strong>，若单纯只是使用key，推荐使用<strong>方式4</strong>。任何情况下都不推荐使用<strong>方式3</strong>，因为会新增二次查询（通过key再一次在Map中查找value）。</p>
<p>另外，使用<strong>方式1</strong>时，还可以做remove操作，这个下面会讲到。</p>
<h3 id="142-iterator的实现原理">1.4.2 Iterator的实现原理</h3>
<p>先看一张类/接口的继承关系图：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094711875.png" class="medium-zoom-image" width="50%"></p>
<p>Iterator为一个顶层接口，只提供了三个基础方法声明：</p>
<pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">Iterator</span>&lt;<span class="hljs-title">E</span>&gt; </span>{
    
  <span class="hljs-function"><span class="hljs-keyword">boolean</span> <span class="hljs-title">hasNext</span><span class="hljs-params">()</span></span>;
    
    <span class="hljs-function">E <span class="hljs-title">next</span><span class="hljs-params">()</span></span>;
    
    <span class="hljs-function"><span class="hljs-keyword">default</span> <span class="hljs-keyword">void</span> <span class="hljs-title">remove</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> UnsupportedOperationException(<span class="hljs-string">"remove"</span>);
    }
}
</code></pre>
<p>这也是我们使用<strong><code>Iterator</code></strong>时绕不开的三个方法。<br>
在HashMap中，首先是新增了一个内部抽象类<strong><code>HashIterator</code></strong>，如下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094736191.png" width="55%"></p>
<p>我们以Entry结点的遍历为例（map的key、value的Iterator遍历方式都类似）：</p>
<pre><code class="language-java hljs">Iterator&lt;Entry&lt;String, Integer&gt;&gt; iterator = testMap.entrySet().iterator();
<span class="hljs-keyword">while</span> (iterator.hasNext()) {
    Entry&lt;String, Integer&gt; next = iterator.next();
    System.out.println(next.getKey() + <span class="hljs-string">":"</span> + next.getValue());
}
</code></pre>
<p>首先，第一行代码，找到<strong><code>Iterator</code></strong>接口的具体实现类<strong><code>EntryIterator</code></strong>：</p>
<pre><code class="language-java hljs"><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">EntryIterator</span> <span class="hljs-keyword">extends</span> <span class="hljs-title">HashIterator</span>&lt;<span class="hljs-title">Map</span>.<span class="hljs-title">Entry</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt;&gt; </span>{
    <span class="hljs-keyword">public</span> Map.<span class="hljs-function">Entry&lt;K,V&gt; <span class="hljs-title">next</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">return</span> nextEntry();
    }
}
</code></pre>
<p>非常简洁有木有？？？就只有一个<strong><code>next()</code></strong>方法，其正是对<strong><code>Iterator</code></strong>接口的<code>next()</code>方法的实现。方法内部也只有一行，指向了父类的<strong><code>nextEntry()</code></strong>方法，即上面截图中的<strong>HashIterator</strong>类中的<code>nextEntry()</code>方法。</p>
<p>HashMap中的Iterator实现原理也不过如此，就是这么朴实无华，是不是都想动手自己撸一个HashMap的实现了？嗯，你可以的！！！</p>
<h2 id="15-fail-fast策略">1.5 fail-fast策略</h2>
<p>和<strong>fail-fast</strong>经常一起出现的还有一个异常类<strong><code>ConcurrentModificationException</code></strong>，接下来我们聊下这两者是什么关系，以及为什么搞这么个策略出来。</p>
<p>什么是<strong>fail-fast</strong>？我们可以称它为"快速失效策略"，下面是Wikipedia中的解释：</p>
<blockquote>
<p>In systems design, a fail-fast system is one which immediately 
reports at its interface any condition that is likely to indicate a 
failure. Fail-fast systems are usually designed to stop normal operation
 rather than attempt to continue a possibly flawed process.<br>
Such designs often check the system's state at several points in an 
operation, so any failures can be detected early. The responsibility of a
 fail-fast module is detecting errors, then letting the next-highest 
level of the system handle them.</p>
</blockquote>
<p>大白话翻译过来，就是在系统设计中，当遇到可能会诱导失败的条件时立即上报错误，快速失效系统往往被设计在立即终止正常操作过程，而不是尝试去继续一个可能会存在错误的过程。<br><br>
<strong>再简洁点说</strong>，就是尽可能早的发现问题，立即终止当前执行过程，由更高层级的系统来做处理。</p>
<p>在HashMap中，我们前面提到的<strong><code>modCount</code></strong>域变量，就是用于实现hashMap中的<strong>fail-fast</strong>。出现这种情况，往往是在非同步的多线程并发操作。<br><br>
在对Map的做迭代(Iterator)操作时，会将<strong><code>modCount</code></strong>域变量赋值给<strong><code>expectedModCount</code></strong>局部变量。在迭代过程中，用于做内容修改次数的一致性校验。若此时有其他线程或本线程的其他操作对此Map做了内容修改时，那么就会导致<strong>modCount</strong>和<strong>expectedModCount</strong>不一致，立即抛出异常<strong><code>ConcurrentModificationException</code></strong>。</p>
<p>举个栗子：</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
  Map&lt;String, Integer&gt; testMap = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();
  testMap.put(<span class="hljs-string">"s1"</span>, <span class="hljs-number">11</span>);
  testMap.put(<span class="hljs-string">"s2"</span>, <span class="hljs-number">22</span>);
  testMap.put(<span class="hljs-string">"s3"</span>, <span class="hljs-number">33</span>);


  <span class="hljs-keyword">for</span> (Map.Entry&lt;String, Integer&gt; entry : testMap.entrySet()) {
      String key = entry.getKey();
      <span class="hljs-keyword">if</span> (<span class="hljs-string">"s1"</span>.equals(key)) {
          testMap.remove(key);
      }
  }
}


---- output ---
Exception in thread <span class="hljs-string">"main"</span> java.util.ConcurrentModificationException
  at java.util.HashMap$HashIterator.nextNode(HashMap.java:<span class="hljs-number">1437</span>)
  at java.util.HashMap$EntryIterator.next(HashMap.java:<span class="hljs-number">1471</span>)
  at java.util.HashMap$EntryIterator.next(HashMap.java:<span class="hljs-number">1469</span>)
    ...
</code></pre>
<p>正确的删除Map元素的姿势：只有一个，Iteator的<strong><code>remove()</code></strong>方法。</p>
<pre><code class="language-java hljs"><span class="hljs-comment">// 方式三</span>
Iterator&lt;Entry&lt;String, Integer&gt;&gt; iterator = testMap.entrySet().iterator();
<span class="hljs-keyword">while</span> (iterator.hasNext()) {
    Entry&lt;String, Integer&gt; next = iterator.next();
    System.out.println(next.getKey() + <span class="hljs-string">":"</span> + next.getValue());
    <span class="hljs-keyword">if</span> (next.getKey().equals(<span class="hljs-string">"s2"</span>)) {
        iterator.remove();
    }
}
</code></pre>
<p>但也要注意一点，能安全删除，并不代表就是多线程安全的，在多线程并发执行时，若都执行上面的操作，因未设置为同步方法，也可能导致<strong><code>modCount</code></strong>与<strong><code>expectedModCount</code></strong>不一致，从而抛异常<strong><code>ConcurrentModificationException</code></strong>。<br>
线程不安全的体现和规避方式，后续章节会详细提及。</p>
<h1 id="二、jdk8中的hashmap底层实现">二、JDK8中的HashMap底层实现</h1>
<p>前面我们已经详细剖析了HashMap在JDK7中的实现，不知大家有没有发现其中可以优化的地方？比如哈希表中因为hash碰撞而产生的链表结
构，如果数据量很大，那么产生碰撞的几率很增加，这带来的后果就是链表长度也一直在增加，对于查询来说，性能会越来越低。如何提升查询性能，成了JDK8
中的HashMap要解决的问题。</p>
<p>因此，相比于JDK7，HashMap在JDK8中做链表结构做了优化（但仍然线程不安全），在一定条件下将链表转为红黑树，提升查询效率。</p>
<p>JDK8中的HashMap其底层存储结构如下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094803971.png" class="medium-zoom-image" width="60%"></p>
<p>相比于JDK7，JDK8中的HashMap会将较长的链表转为红黑树，这也是与JDK7的核心差异。下面先看下<strong><code>put()</code></strong>方法的实现。</p>
<h2 id="21-put操作">2.1 put()操作</h2>
<p>在进一步分析<strong><code>put()</code></strong>操作前，先说明一下：除了底层存储结构有调整，链表结点的定义也由<strong><code>Entry</code></strong>类转为了<strong><code>Node</code></strong>类，但内核没有变化，不影响理解。</p>
<p>先上源代码：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094824961.png" class="medium-zoom-image" width="60%"></p>
<p>是不是很长很复杂？其实不难，只要记住上面的底层存储结构图，代码就很容易看懂。还是一样的存储套路，先根据key确定在哈希table中的下标，找到对应的bucket，遍历链表（或红黑树），做插入操作。在JDK7中，新增结点是使用<strong>头插法</strong>，但在JDK8中，在链表使用<strong>尾插法</strong>，将待新增结点追加到链表末尾。</p>
<p>为方便理解，将上面的代码转为了下面的流程图：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202094852303.png" class="medium-zoom-image" width="80%"></p>
<p><strong>步骤①</strong>：若哈希table为null，或长度为0，则做一次扩容操作；<br>
<strong>步骤②</strong>：根据index找到目标bucket后，若当前bucket上没有结点，那么直接新增一个结点，赋值给该bucket；<br>
<strong>步骤③</strong>：若当前bucket上有链表，且头结点就匹配，那么直接做替换即可；<br>
<strong>步骤④</strong>：若当前bucket上的是树结构，则转为红黑树的插入操作；<br>
<strong>步骤⑤</strong>：若步骤①、②、③、④都不成立，则对链表做遍历操作。<br>
&nbsp;&nbsp;&nbsp; a) 若链表中有结点匹配，则做value替换；<br>
&nbsp;&nbsp;&nbsp; b）若没有结点匹配，则在链表末尾追加。同时，执行以下操作：<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i) 若链表长度大于<code>TREEIFY_THRESHOLD</code>，则执行红黑树转换操作；<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ii) 若<strong>条件i)</strong> 不成立，则执行扩容resize()操作。<br>
以上5步都执行完后，再看当前Map中存储的k-v对的数量是否超出了<strong><code>threshold</code></strong>，若超出，还需再次扩容。</p>
<p>红黑树的转换操作如下：</p>
<pre><code class="language-java hljs"><span class="hljs-comment">/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */</span>
<span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">treeifyBin</span><span class="hljs-params">(Node&lt;K,V&gt;[] tab, <span class="hljs-keyword">int</span> hash)</span> </span>{
    <span class="hljs-keyword">int</span> n, index; Node&lt;K,V&gt; e;
    <span class="hljs-comment">// 若表为空，或表长度小于MIN_TREEIFY_CAPACITY，也不做转换，直接做扩容处理。</span>
    <span class="hljs-keyword">if</span> (tab == <span class="hljs-keyword">null</span> || (n = tab.length) &lt; MIN_TREEIFY_CAPACITY)
        resize();
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((e = tab[index = (n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) {
        TreeNode&lt;K,V&gt; hd = <span class="hljs-keyword">null</span>, tl = <span class="hljs-keyword">null</span>;
        <span class="hljs-keyword">do</span> {
            TreeNode&lt;K,V&gt; p = replacementTreeNode(e, <span class="hljs-keyword">null</span>);
            <span class="hljs-keyword">if</span> (tl == <span class="hljs-keyword">null</span>)
                hd = p;
            <span class="hljs-keyword">else</span> {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);
        <span class="hljs-keyword">if</span> ((tab[index] = hd) != <span class="hljs-keyword">null</span>)
            hd.treeify(tab);
    }
}
</code></pre>
<h2 id="22-扩容操作">2.2 扩容操作</h2>
<p>什么场景下会触发扩容？<br><br>
<strong><font color="red">场景1</font></strong>：哈希table为null或长度为0；<br><br>
<strong><font color="red">场景2</font></strong>：Map中存储的k-v对数量超过了阈值<strong><code>threshold</code></strong>；<br><br>
<strong><font color="red">场景3</font></strong>：链表中的长度超过了<code>TREEIFY_THRESHOLD</code>，但表长度却小于<code>MIN_TREEIFY_CAPACITY</code>。</p>
<p>一般的扩容分为2步，<strong>第1步</strong>是对哈希表长度的扩展（2倍），<strong>第2步</strong>是将旧table中的数据搬到新table上。<br><br>
那么，在JDK8中，HashMap是如何扩容的呢？</p>
<p>上源代码片段：</p>
<pre><code class="language-java hljs">...
<span class="hljs-comment">// 前面已经做了第1步的长度拓展，我们主要分析第2步的操作：如何迁移数据</span>
table = newTab;
<span class="hljs-keyword">if</span> (oldTab != <span class="hljs-keyword">null</span>) {
    <span class="hljs-comment">// 循环遍历哈希table的每个不为null的bucket</span>
    <span class="hljs-comment">// 注意，这里是"++j"，略过了oldTab[0]的处理</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; oldCap; ++j) {
        Node&lt;K,V&gt; e;
        <span class="hljs-keyword">if</span> ((e = oldTab[j]) != <span class="hljs-keyword">null</span>) {
            oldTab[j] = <span class="hljs-keyword">null</span>;
            <span class="hljs-comment">// 若只有一个结点，则原地存储</span>
            <span class="hljs-keyword">if</span> (e.next == <span class="hljs-keyword">null</span>)
                newTab[e.hash &amp; (newCap - <span class="hljs-number">1</span>)] = e;
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (e <span class="hljs-keyword">instanceof</span> TreeNode)
                ((TreeNode&lt;K,V&gt;)e).split(<span class="hljs-keyword">this</span>, newTab, j, oldCap);
            <span class="hljs-keyword">else</span> { <span class="hljs-comment">// preserve order</span>
                <span class="hljs-comment">// "lo"前缀的代表要在原bucket上存储，"hi"前缀的代表要在新的bucket上存储</span>
                <span class="hljs-comment">// loHead代表是链表的头结点，loTail代表链表的尾结点</span>
                Node&lt;K,V&gt; loHead = <span class="hljs-keyword">null</span>, loTail = <span class="hljs-keyword">null</span>;
                Node&lt;K,V&gt; hiHead = <span class="hljs-keyword">null</span>, hiTail = <span class="hljs-keyword">null</span>;
                Node&lt;K,V&gt; next;
                <span class="hljs-keyword">do</span> {
                    next = e.next;
                    <span class="hljs-comment">// 以oldCap=8为例，</span>
                    <span class="hljs-comment">//   0001 1000  e.hash=24</span>
                    <span class="hljs-comment">// &amp; 0000 1000  oldCap=8</span>
                    <span class="hljs-comment">// = 0000 1000  --&gt; 不为0，需要迁移</span>
                    <span class="hljs-comment">// 这种规律可发现，[oldCap, (2*oldCap-1)]之间的数据，</span>
                    <span class="hljs-comment">// 以及在此基础上加n*2*oldCap的数据，都需要做迁移，剩余的则不用迁移</span>
                    <span class="hljs-keyword">if</span> ((e.hash &amp; oldCap) == <span class="hljs-number">0</span>) {
                        <span class="hljs-comment">// 这种是有序插入，即依次将原链表的结点追加到当前链表的末尾</span>
                        <span class="hljs-keyword">if</span> (loTail == <span class="hljs-keyword">null</span>)
                            loHead = e;
                        <span class="hljs-keyword">else</span>
                            loTail.next = e;
                        loTail = e;
                    }
                    <span class="hljs-keyword">else</span> {
                        <span class="hljs-keyword">if</span> (hiTail == <span class="hljs-keyword">null</span>)
                            hiHead = e;
                        <span class="hljs-keyword">else</span>
                            hiTail.next = e;
                        hiTail = e;
                    }
                } <span class="hljs-keyword">while</span> ((e = next) != <span class="hljs-keyword">null</span>);
                <span class="hljs-keyword">if</span> (loTail != <span class="hljs-keyword">null</span>) {
                    loTail.next = <span class="hljs-keyword">null</span>;
                    newTab[j] = loHead;
                }
                <span class="hljs-keyword">if</span> (hiTail != <span class="hljs-keyword">null</span>) {
                    hiTail.next = <span class="hljs-keyword">null</span>;
                    <span class="hljs-comment">// 需要搬迁的结点，新下标为从当前下标往前挪oldCap个距离。</span>
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}
</code></pre>
<h2 id="23-get操作">2.3 get()操作</h2>
<p>了解了上面的put()操作，get()操作就比较简单了。</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">get</span><span class="hljs-params">(Object key)</span> </span>{
    Node&lt;K,V&gt; e;
    <span class="hljs-keyword">return</span> (e = getNode(hash(key), key)) == <span class="hljs-keyword">null</span> ? <span class="hljs-keyword">null</span> : e.value;
}


<span class="hljs-function"><span class="hljs-keyword">final</span> Node&lt;K,V&gt; <span class="hljs-title">getNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, Object key)</span> </span>{
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="hljs-keyword">int</span> n; K k;
    <span class="hljs-keyword">if</span> ((tab = table) != <span class="hljs-keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="hljs-number">0</span> &amp;&amp;
        (first = tab[(n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) {
        <span class="hljs-keyword">if</span> (first.hash == hash &amp;&amp; <span class="hljs-comment">// always check first node</span>
            ((k = first.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
            <span class="hljs-keyword">return</span> first;
        <span class="hljs-keyword">if</span> ((e = first.next) != <span class="hljs-keyword">null</span>) {
            <span class="hljs-keyword">if</span> (first <span class="hljs-keyword">instanceof</span> TreeNode)
                <span class="hljs-keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
            <span class="hljs-keyword">do</span> {
                <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
                    <span class="hljs-keyword">return</span> e;
            } <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
}
</code></pre>
<p>先根据key计算hash值，进一步计算得到哈希table的目标index，若此bucket上为红黑树，则再红黑树上查找，若不是红黑树，遍历链表。</p>
<h1 id="三、hashmap、hashtable是什么关系？">三、HashMap、HashTable是什么关系？</h1>
<p>再把文章开头的这张图放出来，温习一下：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202095007577.png" class="medium-zoom-image" width="55%"></p>
<h2 id="31-共同点与异同点">3.1 共同点与异同点</h2>
<p><strong>共同点</strong>：</p>
<ul>
<li>底层都是使用哈希表 + 链表的实现方式。</li>
</ul>
<p><strong>区别</strong>：</p>
<ul>
<li>从层级结构上看，HashMap、HashTable有一个共用的<strong><code>Map</code></strong>接口。另外，HashTable还单独继承了一个抽象类<strong><code>Dictionary</code></strong>；</li>
<li>HashTable诞生自JDK1.0，HashMap从JDK1.2之后才有；</li>
<li>HashTable线程安全，HashMap线程不安全；</li>
<li>初始值和扩容方式不同。HashTable的初始值为11，扩容为原大小的<code>2*d+1</code>。容量大小都采用奇数且为素数，且采用取模法，这种方式散列更均匀。但有个缺点就是对素数取模的性能较低（涉及到除法运算），而HashTable的长度都是2的次幂，设计就较为巧妙，前面章节也提到过，这种方式的取模都是直接做位运算，性能较好。</li>
<li>HashMap的key、value都可为null，且value可多次为null，key多次为null时会覆盖。当HashTable的key、value都不可为null，否则直接NPE(NullPointException)。</li>
</ul>
<p><strong>示例：</strong></p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
  Map&lt;String, Integer&gt; testTable = <span class="hljs-keyword">new</span> Hashtable&lt;&gt;();
    testTable.put(<span class="hljs-keyword">null</span>, <span class="hljs-number">23</span>);  <span class="hljs-comment">// 抛NPE</span>
    testTable.put(<span class="hljs-string">"s1"</span>, <span class="hljs-keyword">null</span>); <span class="hljs-comment">// 抛NPE</span>
}
</code></pre>
<p>看下<strong><code>put()</code></strong>方法的源码：</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">synchronized</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>{
    <span class="hljs-comment">// Make sure the value is not null</span>
    <span class="hljs-keyword">if</span> (value == <span class="hljs-keyword">null</span>) {
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NullPointerException();
    }


    <span class="hljs-comment">// Makes sure the key is not already in the hashtable.</span>
    Entry&lt;?,?&gt; tab[] = table;
    <span class="hljs-keyword">int</span> hash = key.hashCode();
    <span class="hljs-keyword">int</span> index = (hash &amp; <span class="hljs-number">0x7FFFFFFF</span>) % tab.length;
    <span class="hljs-meta">@SuppressWarnings("unchecked")</span>
    Entry&lt;K,V&gt; entry = (Entry&lt;K,V&gt;)tab[index];
    <span class="hljs-keyword">for</span>(; entry != <span class="hljs-keyword">null</span> ; entry = entry.next) {
        <span class="hljs-keyword">if</span> ((entry.hash == hash) &amp;&amp; entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            <span class="hljs-keyword">return</span> old;
        }
    }


    addEntry(hash, key, value, index);
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
}
</code></pre>
<p>源码中不允许value为null，若为null则直接抛NPE。<br><br>
对于key为null时，源码第9行：<code>int hash = key.hashCode();</code> 未做判空操作，也会外抛NPE。</p>
<p>另外，我们现在看到的抽象类<code>Dictionary</code>，是一个已经废弃的类，源码注释中有如下说明：</p>
<pre><code class="language-java hljs">&lt;strong&gt;NOTE: This <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">is</span> <span class="hljs-title">obsolete</span>.  <span class="hljs-title">New</span> <span class="hljs-title">implementations</span> <span class="hljs-title">should</span>
<span class="hljs-title">implement</span> <span class="hljs-title">the</span> <span class="hljs-title">Map</span> <span class="hljs-title">interface</span>, <span class="hljs-title">rather</span> <span class="hljs-title">than</span> <span class="hljs-title">extending</span> <span class="hljs-title">this</span> <span class="hljs-title">class</span>.&lt;/<span class="hljs-title">strong</span>&gt;
</span></code></pre>
<h2 id="32-hashmap的线程安全">3.2 HashMap的线程安全</h2>
<p>能保证线程线程安全的方式有多个，比如添加<code>synchronized</code>关键字，或者使用<code>lock</code>机制。两者的差异不在此展开，后续会写有关线程安全的文章，到时再详细说明。而HashTable使用了前者，即<code>synchronized</code>关键字。</p>
<p>put操作、get操作、remove操作、equals操作，都使用了<code>synchronized</code>关键字修饰。</p>
<p>这么做是保证了HashTable对象的线程安全特性，但同样也带来了问题，突出问题就是效率低下。为何会说它效率低下呢？<br><br>
因为按synchronized的特性，对于多线程共享的临界资源，同一时刻只能有一个线程在占用，其他线程必须原地等待，为方便理解，大家不妨想下计时用的沙漏，中间最细的瓶颈处阻挡了上方细沙的下落，同样的道理，当有大量线程要执行<code>get()</code>操作时，也存在此类问题，大量线程必须排队一个个处理。</p>
<p>这时可能会有人说，既然<code>get()</code>方法只是获取数据，并没有修改Map的结构和数据，不加不就行了吗？不好意思，不加也
不行，别的方法都加，就你不加，会有一种场景，那就是A线程在做put或remove操作时，B线程、C线程此时都可以同时执行get操作，可能哈希
table已经被A线程改变了，也会带来问题，因此不加也不行。</p>
<p>现在好了，HashMap线程不安全，HashTable虽然线程安全，但性能差，那怎么破？使用<code>ConcurrentHashMap</code>类吧，既线程安全，还操作高效，谁用谁说好。莫急，下面章节会详细解释<code>ConcurrentHashMap</code>类。</p>
<h1 id="四、hashmap线程不安全在哪？">四、HashMap线程不安全在哪？</h1>
<p>本章节主要探讨下HashMap的线程不安全会带来哪些方面的问题。</p>
<h2 id="41-数据覆盖问题">4.1 数据覆盖问题</h2>
<p>两个线程执行<code>put()</code>操作时，可能导致数据覆盖。JDK7版本和JDK8版本的都存在此问题，这里以JDK7为例。</p>
<p>假设A、B两个线程同时执行<code>put()</code>操作，且两个key都指向同一个buekct，那么此时两个结点，都会做头插法。<br>
先看这里的代码实现：</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>{
    ...
    addEntry(hash, key, value, i);
}


<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">addEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>{
    ...
    createEntry(hash, key, value, bucketIndex);
}


<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">createEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>{
    Entry&lt;K,V&gt; e = table[bucketIndex];
    table[bucketIndex] = <span class="hljs-keyword">new</span> Entry&lt;&gt;(hash, key, value, e);
    size++;
}
</code></pre>
<p>看下最后的<code>createEntry()</code>方法，首先获取到了bucket上的头结点，然后再将新结点作为bucket的头部，并指向旧的头结点，完成一次头插法的操作。<br><br>
当线程A和线程B都获取到了bucket的头结点后，若此时线程A的时间片用完，线程B将其新数据完成了头插法操作，此时轮到线程A操作，但这时线程A所
据有的旧头结点已经过时了（并未包含线程B刚插入的新结点），线程A再做头插法操作，就会抹掉B刚刚新增的结点，导致数据丢失。</p>
<p>其实不光是<code>put()</code>操作，删除操作、修改操作，同样都会有覆盖问题。</p>
<h2 id="42-扩容时导致死循环">4.2 扩容时导致死循环</h2>
<p>这是最常遇到的情况，也是面试经常被问及的考题。但说实话，这个多线程环境下导致的死循环问题，并不是那么容易解释清楚，因为这里已经深入到了扩容的细节。这里尽可能简单的描述死循环的产生过程。</p>
<p>另外，只有JDK7及以前的版本会存在死循环现象，在JDK8中，resize()方式已经做了调整，使用两队链表，且都是使用的尾插法，及时多线
程下，也顶多是从头结点再做一次尾插法，不会造成死循环。而JDK7能造成死循环，就是因为resize()时使用了头插法，将原本的顺序做了反转，才留
下了死循环的机会。</p>
<p>在进一步说明死循环的过程前，我们先看下JDK7中的扩容代码片段：</p>
<pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">transfer</span><span class="hljs-params">(Entry[] newTable, <span class="hljs-keyword">boolean</span> rehash)</span> </span>{
    <span class="hljs-keyword">int</span> newCapacity = newTable.length;
    <span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e : table) {
        <span class="hljs-keyword">while</span>(<span class="hljs-keyword">null</span> != e) {
            Entry&lt;K,V&gt; next = e.next;
            <span class="hljs-keyword">if</span> (rehash) {
                e.hash = <span class="hljs-keyword">null</span> == e.key ? <span class="hljs-number">0</span> : hash(e.key);
            }
            <span class="hljs-keyword">int</span> i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
</code></pre>
<p>其实就是简单的链表反转，再进一步简化的话，分为当前结点<code>e</code>，以及下一个结点<code>e.next</code>。我们以链表<code>a-&gt;b-&gt;c-&gt;null</code>为例，两个线程A和B，分别做扩容操作。</p>
<p><strong>原表</strong>：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202095043204.png" width="50%"></p>
<p>线程A和B各自新增了一个新的哈希table，在线程A已做完扩容操作后，线程B才开始扩容。此时对于线程B来说，当前结点<code>e</code>指向a结点，下一个结点<code>e.next</code>仍然指向b结点（此时在线程A的链表中，已经是<code>c-&gt;b-&gt;a</code>的顺序）。按照头插法，哈希表的bucket指向a结点，此时a结点成为线程B中链表的头结点，如下图所示：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202095107611.png" class="medium-zoom-image" width="80%"></p>
<p>a结点成为线程B中链表的头结点后，下一个结点<code>e.next</code>为b结点。既然下一个结点<code>e.next</code>不为null，那么当前结点<code>e</code>就变成了b结点，下一个结点<code>e.next</code>变为a结点。继续执行头插法，将b变为链表的头结点，同时next指针指向旧的头节点a，如下图：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202095125369.png" class="medium-zoom-image" width="80%"></p>
<p>此时，下一个结点<code>e.next</code>为a节点，不为null，继续头插法。指针后移，那么当前结点<code>e</code>就成为了a结点，下一个结点为null。将a结点作为线程B链表中的头结点，并将next指针指向原来的旧头结点b，如下图所示：</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191202095139414.png" class="medium-zoom-image" width="80%"></p>
<p>此时，已形成环链表。同时下一个结点<code>e.next</code>为null，流程结束。</p>
<h2 id="43-小结">4.3 小结</h2>
<p>多线程环境下使用HashMap，会引起各类问题，上面仅为不安全问题的两个典型示例，具体问题无法一一列举，但大体会分为以下三类：</p>
<ul>
<li>死循环</li>
<li>数据重复</li>
<li>数据丢失（覆盖）</li>
</ul>
<p>在JDK1.5之前，多线程环境往往使用HashTable，但在JDK1.5及以后的版本中，在并发包中引入了专门用于多线程环境的<strong><code>ConcurrentHashMap</code></strong>类，采用分段锁实现了线程安全，相比HashTable有更高的性能，推荐使用。</p>
<h1 id="五、如何规避hashmap的线程不安全？">五、如何规避HashMap的线程不安全？</h1>
<p>前面提到了HashMap在多线程环境下的各类不安全问题，那么有哪些方式可以转成线程安全的呢？</p>
<h2 id="51-将map转为包装类">5.1 将Map转为包装类</h2>
<p>如何转？使用<strong><font color="red"><code>Collections.SynchronizedMap()</code></font></strong>方法，示例代码：</p>
<pre><code class="language-java hljs">Map&lt;String, Integer&gt; testMap = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();
...
<span class="hljs-comment">// 转为线程安全的map</span>
Map&lt;String, Integer&gt; map = Collections.synchronizedMap(testMap);
</code></pre>
<p>其内部实现也很简单，等同于HashTable，只是对当前传入的map对象，新增对象锁（synchronized）：</p>
<pre><code class="language-java hljs"><span class="hljs-comment">// 源码来自Collections类</span>


<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SynchronizedMap</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt; <span class="hljs-keyword">implements</span> <span class="hljs-title">Map</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt;, <span class="hljs-title">Serializable</span> </span>{
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">long</span> serialVersionUID = <span class="hljs-number">1978198479659022715L</span>;


    <span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Map&lt;K,V&gt; m;     <span class="hljs-comment">// Backing Map</span>
    <span class="hljs-keyword">final</span> Object      mutex;        <span class="hljs-comment">// Object on which to synchronize</span>


    SynchronizedMap(Map&lt;K,V&gt; m) {
        <span class="hljs-keyword">this</span>.m = Objects.requireNonNull(m);
        mutex = <span class="hljs-keyword">this</span>;
    }


    SynchronizedMap(Map&lt;K,V&gt; m, Object mutex) {
        <span class="hljs-keyword">this</span>.m = m;
        <span class="hljs-keyword">this</span>.mutex = mutex;
    }


    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.size();}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.isEmpty();}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">containsKey</span><span class="hljs-params">(Object key)</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.containsKey(key);}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">containsValue</span><span class="hljs-params">(Object value)</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.containsValue(value);}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">get</span><span class="hljs-params">(Object key)</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.get(key);}
    }


    <span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.put(key, value);}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">remove</span><span class="hljs-params">(Object key)</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {<span class="hljs-keyword">return</span> m.remove(key);}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">putAll</span><span class="hljs-params">(Map&lt;? extends K, ? extends V&gt; map)</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {m.putAll(map);}
    }
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">clear</span><span class="hljs-params">()</span> </span>{
        <span class="hljs-keyword">synchronized</span> (mutex) {m.clear();}
    }
}
</code></pre>
<h2 id="52-使用concurrenthashmap">5.2 使用ConcurrentHashMap</h2>
<p>既然<strong>HashMap</strong>类是线程不安全的，那就不妨找个线程安全的替代品——<strong><code>ConcurrentHashMap</code></strong>类。</p>
<p>使用示例：</p>
<pre><code class="language-java hljs">Map&lt;String, Integer&gt; susuMap = <span class="hljs-keyword">new</span> ConcurrentHashMap&lt;&gt;();
susuMap.put(<span class="hljs-string">"susu1"</span>, <span class="hljs-number">111</span>);
susuMap.put(<span class="hljs-string">"susu2"</span>, <span class="hljs-number">222</span>);
System.out.println(susuMap.get(<span class="hljs-string">"susu1"</span>));
</code></pre>
<p>在使用习惯上完全兼容了HashMap的使用。</p>
<p>JDK1.5版本引入，位于并发包<code>java.util.concurrent</code>下。</p>
<p>在JDK7版本及以前，<strong><code>ConcurrentHashMap</code></strong>类使用了分段锁的技术（segment + Lock），但在jdk8中，也做了较大改动，使用回了synchronized修饰符。<br>
具体差别，在以后的文章中再详细介绍。</p>
<p>文章较长，希望能对在看的你有所帮助。</p>
<blockquote>
<p>更多2019年的技术文章，欢迎关注我的微信公众号：码不停蹄的小鼠松（微信号：busy_squirrel），也可扫下方二维码关注获取最新文章哦~</p>
<p align="center"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191006125707747.png" width="20%"></p>
</blockquote>
<h1 id="reference">Reference</h1>
<p>1、Java 8系列之重新认识HashMap: <a href="https://tech.meituan.com/2016/06/24/java-hashmap.html" target="_blank">https://tech.meituan.com/2016/06/24/java-hashmap.html</a><br>
2、fail-fast是个什么策略？：<a href="http://blog.chinaunix.net/uid-31507842-id-5820534.html" target="_blank">http://blog.chinaunix.net/uid-31507842-id-5820534.html</a></p>

</div>
<div id="MySignature"></div>
<div class="clear"></div>
<div id="blog_post_info_block">
<div id="EntryTag">
    标签: 
            <a href="https://www.cnblogs.com/tianzhihensu/tag/HashMap/">HashMap</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/Java%E9%9D%A2%E8%AF%95/">Java面试</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/HashTable/">HashTable</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/%E6%89%A9%E5%AE%B9/">扩容</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/%E7%BA%BF%E7%A8%8B%E4%B8%8D%E5%AE%89%E5%85%A8/">线程不安全</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/ConcurrentHashMap/">ConcurrentHashMap</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/JDK7/">JDK7</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/JDK8/">JDK8</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/%E7%BA%A2%E9%BB%91%E6%A0%91/">红黑树</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/%E5%93%88%E5%B8%8C%E8%A1%A8/">哈希表</a>,             <a href="https://www.cnblogs.com/tianzhihensu/tag/%E9%93%BE%E8%A1%A8/">链表</a></div>

    <div id="blog_post_info">
<div id="green_channel">
        <a href="javascript:void(0);" id="green_channel_digg" onclick="DiggIt(11972780,cb_blogId,1);green_channel_success(this,'谢谢推荐！');">好文要顶</a>
        <a id="green_channel_follow" onclick="follow('1544eed0-b6cb-e411-b908-9dcfd8948a71');" href="javascript:void(0);">关注我</a>
    <a id="green_channel_favorite" onclick="AddToWz(cb_entryId);return false;" href="javascript:void(0);">收藏该文</a>
    <a id="green_channel_weibo" href="javascript:void(0);" title="分享至新浪微博" onclick="ShareToTsina()"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/icon_weibo_24.png" alt=""></a>
    <a id="green_channel_wechat" href="javascript:void(0);" title="分享至微信" onclick="shareOnWechat()"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/wechat.png" alt=""></a>
</div>
<div id="author_profile">
    <div id="author_profile_info" class="author_profile_info">
            <a href="https://home.cnblogs.com/u/tianzhihensu/" target="_blank"><img src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/20191203173217.png" class="author_avatar" alt=""></a>
        <div id="author_profile_detail" class="author_profile_info">
            <a href="https://home.cnblogs.com/u/tianzhihensu/">天之痕苏的小院子</a><br>
            <a href="https://home.cnblogs.com/u/tianzhihensu/followees/">关注 - 1</a><br>
            <a href="https://home.cnblogs.com/u/tianzhihensu/followers/">粉丝 - 1</a>
        </div>
    </div>
    <div class="clear"></div>
    <div id="author_profile_honor"></div>
    <div id="author_profile_follow">
                <a href="javascript:void(0);" onclick="follow('1544eed0-b6cb-e411-b908-9dcfd8948a71');return false;">+加关注</a>
    </div>
</div>
<div id="div_digg">
    <div class="diggit" onclick="votePost(11972780,'Digg')">
        <span class="diggnum" id="digg_count">2</span>
    </div>
    <div class="buryit" onclick="votePost(11972780,'Bury')">
        <span class="burynum" id="bury_count">0</span>
    </div>
    <div class="clear"></div>
    <div class="diggword" id="digg_tips">
    </div>
</div>

<script type="text/javascript">
    currentDiggType = 0;
</script></div>
    <div class="clear"></div>
    <div id="post_next_prev">


</div>
</div>
            </div>
            <div class="postDesc">posted @ 
<span id="post-date">2019-12-02 19:26</span>&nbsp;
<a href="https://www.cnblogs.com/tianzhihensu/">天之痕苏的小院子</a>&nbsp;
阅读(<span id="post_view_count">5622</span>)&nbsp;
评论(<span id="post_comment_count">5</span>)&nbsp;
<a href="https://i.cnblogs.com/EditPosts.aspx?postid=11972780" rel="nofollow">编辑</a>&nbsp;
<a href="javascript:void(0)" onclick="AddToWz(11972780);return false;">收藏</a></div>
        </div>
	    
	    
    </div><!--end: topics 文章、评论容器-->
</div>
<script src="HashMap%E9%9D%A2%E8%AF%95%E9%A2%98_files/highlight.js"></script>
<script>markdown_highlight();</script>
<script>
    var allowComments = true, cb_blogId = 218355, cb_blogApp = 'tianzhihensu', cb_blogUserGuid = '1544eed0-b6cb-e411-b908-9dcfd8948a71';
    var cb_entryId = 11972780, cb_entryCreatedDate = '2019-12-02 19:26', cb_postType = 1;
    updatePostStats(
        [cb_entryId],
        function(id, count) { $("#post_view_count").text(count) },
        function(id, count) { $("#post_comment_count").text(count) })
    zoomManager.apply("#cnblogs_post_body img:not(.code_img_closed):not(.code_img_opened)");
</script>
<a name="!comments"></a>
<div id="blog-comments-placeholder">

<div id="comment_pager_top">
    
</div>

<br>
<div class="feedback_area_title">评论列表</div>
<div class="feedbackNoItems">
    <div class="feedbackNoItems"></div>
</div>
    <div class="feedbackItem">
        <div class="feedbackListSubtitle">
            <div class="feedbackManage">
                &nbsp;&nbsp;

<span class="comment_actions">
    
    
    
    
</span>


            </div>
            
<a href="#4544933" class="layer">#1楼</a>
<a name="4544933" id="comment_anchor_4544933"></a>
 
<span class="comment_date">2020-04-08 17:05</span>

 
        <a id="a_comment_author_4544933" href="https://www.cnblogs.com/nwz-fly/" target="_blank">让土块飞</a>

        </div>
        <div class="feedbackCon">
            
<div id="comment_body_4544933" data-format-type="Markdown" class="blog_comment_body cnblogs-markdown">
    <p>写的很清晰了</p>

</div>
        <div class="comment_vote">
            <span class="comment_error" style="color: red"></span>
            <a href="javascript:void(0);" class="comment_digg" onclick="return voteComment(4544933, 'Digg', this.parentElement, false);">
                支持(0)
            </a>
            <a href="javascript:void(0);" class="comment_burry" onclick="return voteComment(4544933, 'Bury', this.parentElement, false);">
                反对(0)
            </a>
        </div>
        <span id="comment_4544933_avatar" style="display:none">
            https://pic.cnblogs.com/face/1009302/20161228161903.png
        </span>

        </div>
    </div>
    <div class="feedbackItem">
        <div class="feedbackListSubtitle">
            <div class="feedbackManage">
                &nbsp;&nbsp;

<span class="comment_actions">
    
    
    
    
</span>


            </div>
            
<a href="#4544952" class="layer">#2楼</a>
<a name="4544952" id="comment_anchor_4544952"></a>
 
<span class="comment_date">2020-04-08 17:15</span>

 
        <a id="a_comment_author_4544952" href="https://www.cnblogs.com/nwz-fly/" target="_blank">让土块飞</a>

        </div>
        <div class="feedbackCon">
            
<div id="comment_body_4544952" data-format-type="Markdown" class="blog_comment_body cnblogs-markdown">
    <p>第一张类图，HashTable的继承类写错了 是Dictionary不是Directory</p>

</div>
        <div class="comment_vote">
            <span class="comment_error" style="color: red"></span>
            <a href="javascript:void(0);" class="comment_digg" onclick="return voteComment(4544952, 'Digg', this.parentElement, false);">
                支持(1)
            </a>
            <a href="javascript:void(0);" class="comment_burry" onclick="return voteComment(4544952, 'Bury', this.parentElement, false);">
                反对(0)
            </a>
        </div>
        <span id="comment_4544952_avatar" style="display:none">
            https://pic.cnblogs.com/face/1009302/20161228161903.png
        </span>

        </div>
    </div>
    <div class="feedbackItem">
        <div class="feedbackListSubtitle">
            <div class="feedbackManage">
                &nbsp;&nbsp;

<span class="comment_actions">
    
    
    
    
</span>


            </div>
            
<a href="#4593276" class="layer">#3楼</a>
<a name="4593276" id="comment_anchor_4593276"></a>
 
<span class="comment_date">2020-06-02 11:18</span>

 
        <a id="a_comment_author_4593276" href="https://www.cnblogs.com/andydlz/" target="_blank">温榆河畔的男人</a>

        </div>
        <div class="feedbackCon">
            
<div id="comment_body_4593276" data-format-type="Markdown" class="blog_comment_body cnblogs-markdown">
    <p>头一句就错了 哈希表+链表？说错了吧？哈希表本身即是数组+链表</p>

</div>
        <div class="comment_vote">
            <span class="comment_error" style="color: red"></span>
            <a href="javascript:void(0);" class="comment_digg" onclick="return voteComment(4593276, 'Digg', this.parentElement, false);">
                支持(1)
            </a>
            <a href="javascript:void(0);" class="comment_burry" onclick="return voteComment(4593276, 'Bury', this.parentElement, false);">
                反对(0)
            </a>
        </div>
        

        </div>
    </div>
    <div class="feedbackItem">
        <div class="feedbackListSubtitle">
            <div class="feedbackManage">
                &nbsp;&nbsp;

<span class="comment_actions">
    
    
    
    
</span>


            </div>
            
<a href="#4766132" class="layer">#4楼</a>
<a name="4766132" id="comment_anchor_4766132"></a>
 
<span class="comment_date">2020-12-08 09:58</span>

 
        <a id="a_comment_author_4766132" href="https://www.cnblogs.com/tjs800/" target="_blank">java小黑3</a>

        </div>
        <div class="feedbackCon">
            
<div id="comment_body_4766132" data-format-type="Markdown" class="blog_comment_body cnblogs-markdown">
    <p>注意，这里是"<ins>j"，略过了oldTab[0]的处理<br>
fori循环, **i</ins>和++i**没有任何区别好吧.</p>
<pre><code class="hljs csharp">        <span class="hljs-keyword">for</span> (<span class="hljs-built_in">int</span> j = <span class="hljs-number">0</span>; j &lt; <span class="hljs-number">3</span>; ++j) {
            System.<span class="hljs-keyword">out</span>.println(j);
        }
       <span class="hljs-comment">//result: 0,1,2</span>
</code></pre>

</div>
        <div class="comment_vote">
            <span class="comment_error" style="color: red"></span>
            <a href="javascript:void(0);" class="comment_digg" onclick="return voteComment(4766132, 'Digg', this.parentElement, false);">
                支持(0)
            </a>
            <a href="javascript:void(0);" class="comment_burry" onclick="return voteComment(4766132, 'Bury', this.parentElement, false);">
                反对(0)
            </a>
        </div>
        <span id="comment_4766132_avatar" style="display:none">
            https://pic.cnblogs.com/face/2216855/20201117112333.png
        </span>

        </div>
    </div>
    <div class="feedbackItem">
        <div class="feedbackListSubtitle">
            <div class="feedbackManage">
                &nbsp;&nbsp;

<span class="comment_actions">
    
    
    
    
</span>


            </div>
            
<a href="#4766144" class="layer">#5楼</a>
<a name="4766144" id="comment_anchor_4766144"></a>
    <span id="comment-maxId" style="display: none">4766144</span>
    <span id="comment-maxDate" style="display: none">2020/12/8 上午10:08:26</span>
 
<span class="comment_date">2020-12-08 10:08</span>

 
        <a id="a_comment_author_4766144" href="https://www.cnblogs.com/tjs800/" target="_blank">java小黑3</a>

        </div>
        <div class="feedbackCon">
            
<div id="comment_body_4766144" data-format-type="Markdown" class="blog_comment_body cnblogs-markdown">
    <blockquote>
<p>// 若只有一个结点，则原地存储<br>
if (e.next == null)<br>
newTab[e.hash &amp; (newCap - 1)] = e;</p>
</blockquote>
<p>这叫原地存储?????</p>

</div>
        <div class="comment_vote">
            <span class="comment_error" style="color: red"></span>
            <a href="javascript:void(0);" class="comment_digg" onclick="return voteComment(4766144, 'Digg', this.parentElement, false);">
                支持(0)
            </a>
            <a href="javascript:void(0);" class="comment_burry" onclick="return voteComment(4766144, 'Bury', this.parentElement, false);">
                反对(0)
            </a>
        </div>
        <span id="comment_4766144_avatar" style="display:none">
            https://pic.cnblogs.com/face/2216855/20201117112333.png
        </span>

        </div>
    </div>

<div id="comment_pager_bottom">
    
</div>


</div>
<div id="comment_form" class="commentform">
    <a name="commentform"></a>
    <div id="divCommentShow"></div>
    <div id="comment_nav"><span id="span_refresh_tips"></span><a href="javascript:void(0);" onclick="return RefreshCommentList();" id="lnk_RefreshComments" runat="server" clientidmode="Static">刷新评论</a><a href="#" onclick="return RefreshPage();">刷新页面</a><a href="#top">返回顶部</a></div>
    <div id="comment_form_container" style="visibility: visible;"><div class="login_tips">
    登录后才能发表评论，立即 <a rel="nofollow" href="javascript:void(0);" class="underline" onclick="return login('commentform');">登录</a> 或
    <a rel="nofollow" href="javascript:void(0);" class="underline" onclick="return register();">注册</a>，
    <a href="https://www.cnblogs.com/">访问</a> 网站首页
</div>
</div>
    <div class="ad_text_commentbox" id="ad_text_under_commentbox"></div>
    <div id="ad_t2"><a href="http://www.uccpsoft.com/index.htm" target="_blank" onclick="ga('send', 'event', 'Link', 'click', 'T2-ucancode')">【推荐】大型组态、工控、仿真、CAD\GIS 50万行VC++源码免费下载!</a><br><a href="https://www.cnblogs.com/cmt/p/14408628.html" target="_blank" onclick="ga('send', 'event', 'Link', 'click', 'T2-AWS')">【求助】注册 Amazon Web Services(AWS) 账户，助园子一臂之力</a><br><a href="https://brands.cnblogs.com/huawei" target="_blank" onclick="ga('send', 'event', 'Link', 'click', 'T2-华为专区')">【推荐】万物互联的时代，由你的代码定义，创建HarmonyOS应用</a><br><a href="http://www.javamall.com.cn/" target="_blank" onclick="ga('send', 'event', 'Link', 'click', 'T2-javashop')">【推荐】Javashop--基于SPRING BOOT架构的企业级电商系统</a><br></div>
    <div id="opt_under_post"></div>
    <div id="cnblogs_c1" class="under-post-card">
        <div id="div-gpt-ad-1592365906576-0" style="width: 300px; height: 250px;" data-google-query-id="CLiKvqzXmu8CFRAsYAod8bUPbg"><div id="google_ads_iframe_/1090369/C1_0__container__" style="border: 0pt none;"><iframe id="google_ads_iframe_/1090369/C1_0" title="3rd party ad content" name="google_ads_iframe_/1090369/C1_0" scrolling="no" marginwidth="0" marginheight="0" style="border: 0px none; vertical-align: bottom;" srcdoc="" data-google-container-id="1" data-load-complete="true" width="300" height="250" frameborder="0"></iframe></div></div>
    </div>
    <div id="under_post_card1"><div class="under-post-card"><b>AWS免费产品</b>：<br>· <a onclick='ga("send", "event", "Link", "click", "aws-underpost-card")' href="https://aws.amazon.com/cn/free/webapps/?trk=ba_a134p000006vc6OAAQ&amp;trkCampaign=webapps&amp;sc_channel=ba&amp;sc_campaign=cnblogs&amp;sc_outcome=Acquisition&amp;sc_geo=CHNA&amp;sc_country=CN&amp;sc_publisher=Others" target="_blank">如何在AWS上免费构建网站</a><br>· <a onclick='ga("send", "event", "Link", "click", "aws-underpost-card")' href="https://aws.amazon.com/cn/free/storage/?trk=ba_a134p000006vc7JAAQ&amp;trkCampaign=storage&amp;sc_channel=ba&amp;sc_campaign=cnblogs&amp;sc_outcome=Acquisition&amp;sc_geo=CHNA&amp;sc_country=CN&amp;sc_publisher=Others" target="_blank">AWS免费云存储解决方案</a><br>· <a onclick='ga("send", "event", "Link", "click", "aws-underpost-card")' href="https://aws.amazon.com/cn/free/database/?trk=ba_a134p000006vc7YAAQ&amp;trkCampaign=database&amp;sc_channel=ba&amp;sc_campaign=cnblogs&amp;sc_outcome=Acquisition&amp;sc_geo=CHNA&amp;sc_country=CN&amp;sc_publisher=Others" target="_blank">在AWS上免费构建数据库</a><br>· <a onclick='ga("send", "event", "Link", "click", "aws-underpost-card")' href="https://aws.amazon.com/cn/free/machine-learning/?trk=ba_a134p000006vc7nAAA&amp;trkCampaign=ML&amp;sc_channel=ba&amp;sc_campaign=cnblogs&amp;sc_outcome=Acquisition&amp;sc_geo=CHNA&amp;sc_country=CN&amp;sc_publisher=Others" target="_blank">AWS上的免费机器学习</a></div></div>
    <div id="cnblogs_c2" class="under-post-card">
        <div id="div-gpt-ad-1592366332455-0" style="width: 468px; height: 60px;" data-google-query-id="CLmKvqzXmu8CFRAsYAod8bUPbg"><div id="google_ads_iframe_/1090369/C2_0__container__" style="border: 0pt none;"><iframe id="google_ads_iframe_/1090369/C2_0" title="3rd party ad content" name="google_ads_iframe_/1090369/C2_0" scrolling="no" marginwidth="0" marginheight="0" style="border: 0px none; vertical-align: bottom;" srcdoc="" data-google-container-id="2" data-load-complete="true" width="468" height="60" frameborder="0"></iframe></div></div>
    </div>
    <div id="under_post_card2"><div class="itnews under-post-card">
    <b>最新新闻</b>：
    <br>
 ·          <a href="https://news.cnblogs.com/n/689603/" target="_blank">被围殴的pdd、打假赛的选手：假赛阴云包围下的中国电竞</a>
        <br>
 ·          <a href="https://news.cnblogs.com/n/689602/" target="_blank">苹果是运气股，不是价值股</a>
        <br>
 ·          <a href="https://news.cnblogs.com/n/689601/" target="_blank">销量骤降，宝沃最终还是被陆正耀拖累了</a>
        <br>
 ·          <a href="https://news.cnblogs.com/n/689600/" target="_blank">美毅力号在火星上迈出第一步：可以边行驶边思考</a>
        <br>
 ·          <a href="https://news.cnblogs.com/n/689599/" target="_blank">首次超越华为：OPPO成中国最大智能手机制造商</a>
        <br>
    » <a href="https://news.cnblogs.com/" title="IT 新闻" target="_blank">更多新闻...</a>
</div></div>
    <div id="HistoryToday" class="under-post-card"></div>
    <script type="text/javascript">
       var commentManager = new blogCommentManager();
       commentManager.renderComments(0);
       fixPostBody();
       deliverBigBanner();
setTimeout(function() { incrementViewCount(cb_entryId); }, 50);       deliverT2();
       deliverC1C2();
       loadNewsAndKb();
       loadBlogSignature();
LoadPostCategoriesTags(cb_blogId, cb_entryId);       LoadPostInfoBlock(cb_blogId, cb_entryId, cb_blogApp, cb_blogUserGuid);
       GetPrevNextPost(cb_entryId, cb_blogId, cb_entryCreatedDate, cb_postType);
       loadOptUnderPost();
       GetHistoryToday(cb_blogId, cb_blogApp, cb_entryCreatedDate);
    </script>
</div>

	</div><!--end: forFlow -->
	</div><!--end: mainContent 主体内容容器-->
	<div id="sideBar">
		<div id="sideBarMain">
			<div id="sidebar_news" class="newsItem"><!--done-->
<h3 class="catListTitle">公告</h3>

<div id="blog-news">
    
    <div id="profile_block">
        昵称：
        <a href="https://home.cnblogs.com/u/tianzhihensu/">
            天之痕苏的小院子
        </a>
        <br>
        园龄：
        <a href="https://home.cnblogs.com/u/tianzhihensu/" title="入园时间：2015-03-16">
            5年11个月
        </a>
        <br>
        粉丝：
        <a href="https://home.cnblogs.com/u/tianzhihensu/followers/">
            1
        </a>
        <br>
        关注：
        <a href="https://home.cnblogs.com/u/tianzhihensu/followees/">
            1
        </a>
        <div id="p_b_follow">
<a href="javascript:void(0)" onclick="follow('1544eed0-b6cb-e411-b908-9dcfd8948a71')">+加关注</a></div>
        <script>getFollowStatus('1544eed0-b6cb-e411-b908-9dcfd8948a71');</script>
    </div>
</div>

</div>
<div id="sidebar_c3"></div>
			<div id="blog-calendar" style="">

<table id="blogCalendar" class="Cal" title="Calendar" cellspacing="0" cellpadding="0" border="0">
    <tbody>
        <tr>
            <td colspan="7">
                <table class="CalTitle" cellspacing="0" border="0">
                    <tbody>
                        <tr>
                            <td class="CalNextPrev">
                                <a href="javascript:void(0);" onclick="loadBlogCalendar('2021/02/06'); return false;">&lt;</a>
                            </td>
                            <td align="center">2021年3月</td>
                            <td class="CalNextPrev" align="right">
                                <a href="javascript:void(0);" onclick="loadBlogCalendar('2021/04/06'); return false;">&gt;</a>
                            </td>
                        </tr>
                    </tbody>
                </table>
            </td>
        </tr>
    <tr>
        <th class="CalDayHeader" abbr="日" scope="col" align="center">日</th>
        <th class="CalDayHeader" abbr="一" scope="col" align="center">一</th>
        <th class="CalDayHeader" abbr="二" scope="col" align="center">二</th>
        <th class="CalDayHeader" abbr="三" scope="col" align="center">三</th>
        <th class="CalDayHeader" abbr="四" scope="col" align="center">四</th>
        <th class="CalDayHeader" abbr="五" scope="col" align="center">五</th>
        <th class="CalDayHeader" abbr="六" scope="col" align="center">六</th>
    </tr>
            <tr>
                            <td class="CalOtherMonthDay" align="center">28</td>
                        <td class="" align="center">
                            1
                        </td>
                        <td class="" align="center">
                            2
                        </td>
                        <td class="" align="center">
                            3
                        </td>
                        <td class="" align="center">
                            4
                        </td>
                        <td class="" align="center">
                            5
                        </td>
                    <td class="CalTodayDay" align="center">
                        6
                    </td>
            </tr>
                <tr>
                        <td class="CalWeekendDay" align="center">
                            7
                        </td>
                            <td class="" align="center">
                                8
                            </td>
                            <td class="" align="center">
                                9
                            </td>
                            <td class="" align="center">
                                10
                            </td>
                            <td class="" align="center">
                                11
                            </td>
                            <td class="" align="center">
                                12
                            </td>
                        <td class="CalWeekendDay" align="center">
                            13
                        </td>
                </tr>
                <tr>
                        <td class="CalWeekendDay" align="center">
                            14
                        </td>
                            <td class="" align="center">
                                15
                            </td>
                            <td class="" align="center">
                                16
                            </td>
                            <td class="" align="center">
                                17
                            </td>
                            <td class="" align="center">
                                18
                            </td>
                            <td class="" align="center">
                                19
                            </td>
                        <td class="CalWeekendDay" align="center">
                            20
                        </td>
                </tr>
                <tr>
                        <td class="CalWeekendDay" align="center">
                            21
                        </td>
                            <td class="" align="center">
                                22
                            </td>
                            <td class="" align="center">
                                23
                            </td>
                            <td class="" align="center">
                                24
                            </td>
                            <td class="" align="center">
                                25
                            </td>
                            <td class="" align="center">
                                26
                            </td>
                        <td class="CalWeekendDay" align="center">
                            27
                        </td>
                </tr>
                <tr>
                        <td class="CalWeekendDay" align="center">
                            28
                        </td>
                            <td class="" align="center">
                                29
                            </td>
                            <td class="" align="center">
                                30
                            </td>
                            <td class="" align="center">
                                31
                            </td>
                            <td class="CalOtherMonthDay" align="center">
                                1
                            </td>
                            <td class="CalOtherMonthDay" align="center">
                                2
                            </td>
                        <td class="CalOtherMonthDay" align="center">
                            3
                        </td>
                </tr>
                <tr>
                        <td class="CalOtherMonthDay" align="center">
                            4
                        </td>
                            <td class="CalOtherMonthDay" align="center">
                                5
                            </td>
                            <td class="CalOtherMonthDay" align="center">
                                6
                            </td>
                            <td class="CalOtherMonthDay" align="center">
                                7
                            </td>
                            <td class="CalOtherMonthDay" align="center">
                                8
                            </td>
                            <td class="CalOtherMonthDay" align="center">
                                9
                            </td>
                        <td class="CalOtherMonthDay" align="center">
                            10
                        </td>
                </tr>
    </tbody>
</table></div><script>loadBlogDefaultCalendar();</script>			
			<div id="leftcontentcontainer">
				<div id="blog-sidecolumn"><!-- 搜索 -->
<div id="sidebar_search" class="sidebar-block">
    <div id="sidebar_search" class="mySearch">
        <h3 class="catListTitle">搜索</h3>
        <div id="sidebar_search_box">
            <div id="widget_my_zzk" class="div_my_zzk">
                <input type="text" id="q" onkeydown="return zzk_go_enter(event);" class="input_my_zzk">&nbsp;<input onclick="zzk_go()" type="button" value="找找看" id="btnZzk" class="btn_my_zzk">
            </div>
            <div id="widget_my_google" class="div_my_zzk">
                <input type="text" name="google_q" id="google_q" onkeydown="return google_go_enter(event);" class="input_my_zzk">&nbsp;<input onclick="google_go()" type="button" value="谷歌搜索" class="btn_my_zzk">
            </div>
        </div>
    </div>
</div>

<!-- 常用链接 -->
<div id="sidebar_shortcut" class="sidebar-block"><div class="catListLink">
<h3 class="catListTitle">
常用链接
</h3>
<ul>
    
<li><a href="https://www.cnblogs.com/tianzhihensu/p/" title="我的博客的随笔列表">我的随笔</a></li>
<li><a href="https://www.cnblogs.com/tianzhihensu/MyComments.html" title="我的发表过的评论列表">我的评论</a></li>
<li><a href="https://www.cnblogs.com/tianzhihensu/OtherPosts.html" title="我评论过的随笔列表">我的参与</a></li>
<li><a href="https://www.cnblogs.com/tianzhihensu/RecentComments.html" title="我的博客的评论列表">最新评论</a></li>
<li><a href="https://www.cnblogs.com/tianzhihensu/tag/" title="我的博客的标签列表">我的标签</a></li>

</ul>
</div>

</div>

<!-- 最新随笔 -->


<!-- 我的标签 -->
<div id="sidebar_toptags" class="sidebar-block"><div class="catListTag">
<h3 class="catListTitle">我的标签</h3>
<ul>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/ConcurrentHashMap/">ConcurrentHashMap<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/HashMap/">HashMap<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/HashTable/">HashTable<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/Java%E9%9D%A2%E8%AF%95/">Java面试<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/JDK7/">JDK7<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/JDK8/">JDK8<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/%E5%93%88%E5%B8%8C%E8%A1%A8/">哈希表<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/%E7%BA%A2%E9%BB%91%E6%A0%91/">红黑树<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/%E6%89%A9%E5%AE%B9/">扩容<span class="tag-count">(1)</span></a>
        </li>
        <li>
            <a href="https://www.cnblogs.com/tianzhihensu/tag/%E9%93%BE%E8%A1%A8/">链表<span class="tag-count">(1)</span></a>
        </li>
    <li>
        <a href="https://www.cnblogs.com/tianzhihensu/tag/">更多</a>
    </li>

</ul>
</div>

</div>

<!-- 积分与排名 -->


<!-- 随笔分类、随笔档案、文章分类、新闻分类、相册、链接 -->
<div id="sidebar_categories">

    <div id="sidebar_postarchive" class="catListPostArchive sidebar-block">
        <h3 class="catListTitle">
            
随笔档案



        </h3>

        <ul>

                <li data-category-list-item-visible="true" style="display: block">
                    
<a href="https://www.cnblogs.com/tianzhihensu/archive/2019/12.html" rel="" target="">
    2019年12月(1)
</a>
 

                </li>                
                <li data-category-list-item-visible="true" style="display: block">
                    
<a href="https://www.cnblogs.com/tianzhihensu/archive/2016/02.html" rel="" target="">
    2016年2月(5)
</a>
 

                </li>                
                <li data-category-list-item-visible="true" style="display: block">
                    
<a href="https://www.cnblogs.com/tianzhihensu/archive/2015/12.html" rel="" target="">
    2015年12月(5)
</a>
 

                </li>                
                <li data-category-list-item-visible="true" style="display: block">
                    
<a href="https://www.cnblogs.com/tianzhihensu/archive/2015/11.html" rel="" target="">
    2015年11月(37)
</a>
 

                </li>                
            
        </ul>


    </div>    
    <div id="sidebar_imagecategory" class="catListImageCategory sidebar-block">
        <h3 class="catListTitle">
            
相册



        </h3>

        <ul>

                <li data-category-list-item-visible="true" style="display: block">
                    
<a href="https://www.cnblogs.com/tianzhihensu/gallery/985239.html" rel="nofollow noopener noreferrer" target="">
    毕业论文素材相册(38)
</a>
 

                </li>                
            
        </ul>


    </div>    
</div>

<!-- 最新评论 -->
<div id="sidebar_recentcomments" class="sidebar-block"><div class="catListComment">
<h3 class="catListTitle">最新评论</h3>

	<div class="RecentCommentBlock">
        <ul>
                    <li class="recent_comment_title"><a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">1. Re:HashMap面试题，看这一篇就够了！</a></li>
                    <li class="recent_comment_body">// 若只有一个结点，则原地存储 if (e.next == null) newTab[e.hash &amp; (newCap - 1)] = e; 这叫原地存储?????...</li>
                    <li class="recent_comment_author">--java小黑3</li>
                    <li class="recent_comment_title"><a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">2. Re:HashMap面试题，看这一篇就够了！</a></li>
                    <li class="recent_comment_body">注意，这里是"j"，略过了oldTab[0]的处理 fori循环, **i和++i**没有任何区别好吧. for (int j = 0; j &lt; 3; ++j) { System.out.printl...</li>
                    <li class="recent_comment_author">--java小黑3</li>
                    <li class="recent_comment_title"><a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">3. Re:HashMap面试题，看这一篇就够了！</a></li>
                    <li class="recent_comment_body"><p>头一句就错了 哈希表+链表？说错了吧？哈希表本身即是数组+链表</p>
</li>
                    <li class="recent_comment_author">--温榆河畔的男人</li>
                    <li class="recent_comment_title"><a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">4. Re:HashMap面试题，看这一篇就够了！</a></li>
                    <li class="recent_comment_body"><p>第一张类图，HashTable的继承类写错了 是Dictionary不是Directory</p>
</li>
                    <li class="recent_comment_author">--让土块飞</li>
                    <li class="recent_comment_title"><a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">5. Re:HashMap面试题，看这一篇就够了！</a></li>
                    <li class="recent_comment_body"><p>写的很清晰了</p>
</li>
                    <li class="recent_comment_author">--让土块飞</li>
        </ul>
    </div>
</div>

</div>


<!-- 阅读排行榜 -->
<div id="sidebar_topviewedposts" class="sidebar-block"><div class="catListView">
<h3 class="catListTitle">阅读排行榜</h3>
	<div id="TopViewPostsBlock">
        <ul style="word-break:break-all">
                    <li>
                        <a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">
                            1. HashMap面试题，看这一篇就够了！(5622)
                        </a>
                    </li>
        </ul>
    </div>
</div>

</div>

<!-- 评论排行榜 -->
<div id="sidebar_topcommentedposts" class="sidebar-block"><div class="catListFeedback">
<h3 class="catListTitle">评论排行榜</h3>
	<div id="TopFeedbackPostsBlock">
        <ul style="word-break:break-all">
                    <li>
                        <a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">
                            1. HashMap面试题，看这一篇就够了！(5)
                        </a>
                    </li>
        </ul>
    </div>
</div>

</div>

<!-- 推荐排行榜 -->
<div id="sidebar_topdiggedposts" class="sidebar-block">
<div id="topdigg_posts_wrap">
    <div class="catListView">
        <h3 class="catListTitle">推荐排行榜</h3>
        <div id="TopDiggPostsBlock">
            <ul style="word-break: break-all">
                        <li>
                            <a href="https://www.cnblogs.com/tianzhihensu/p/11972780.html">
                                1. HashMap面试题，看这一篇就够了！(2)
                            </a>
                        </li>
            </ul>
        </div>
    </div>
</div></div></div>
                    <script>loadBlogSideColumn();</script>
			</div>			
		</div><!--end: sideBarMain -->
	</div><!--end: sideBar 侧边栏容器 -->
	<div class="clear"></div>
	</div><!--end: main -->
	<div class="clear"></div>
	<div id="footer">
		<!--done-->
Copyright © 2021 天之痕苏的小院子
<br><span id="poweredby">Powered by .NET 5.0 on Kubernetes</span>



	</div><!--end: footer -->
</div><!--end: home 自定义的最大容器 -->


    

    <input type="hidden" id="antiforgery_token" value="CfDJ8EklyHYHyB5Oj4onWtxTnxaZ8MX5HUobLpIGHz60rYQAf3A9-BVGU7t63ZD0eMVBlR4if7CfC1Mnh7HWVhEcdLILGGQ_opO72VLWpH2nuIr8Mr6r9Pimo3zsKuxCfVBEcxvZ86rwOVgd6Q9YVh3F3Oc">


<iframe id="google_osd_static_frame_6225903075524" name="google_osd_static_frame" style="display: none; width: 0px; height: 0px;"></iframe></body></html>